(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Biodiversity Heritage Library | Children's Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "General theory of most efficient codes"

"LI E> HAHY 

OF THE 
UNIVERSITY 
OF ILLINOIS 

510.84 

I26T 

no. 156-163 

cop 2 



Digitized by the Internet Archive 
in 2013 



http://archive.org/details/generaltheoryofm163koma 



fC\ S4- DIGITAL COMJ'U'PKK LABORATORY 

^ ^ "*" UNIVERSITY OF ILLINOIS 

^p ^ URBANA, ILLINOIS 



REPORT NO. 163 



GENERAL THEORY OF MOST EFFICIENT CODES 

by 
Yasuo Komamiya 






June 9, 196^ 



The person charging this material is re- 
sponsible for its return on or before the 
Latest Date stamped below. 

Theft, mutilation, and underlining of books 
are reasons for disciplinary action and may 
result in dismissal from the University. 

University of Illinois Library 







ACKNOWLEDGMENT 

The author wishes to thank Professor David E. Muller for a number of 
helpful discussions in connection with this report, and Mrs. Phyllis Olson for 
her skillful typing of this paper. 



TABLE OF CONTENTS 

Page 

1. INTRODUCTION 

2. A THEOREM WHICH PLAYS AN IMPORTANT ROLE IN THE CODING PROBLEM . . 3 

3. GENERAL THEORY OF MOST EFFICIENT CODES L3 

k. CALCULATION AND SOME PROPERTIES OF EACH \ 28 

l 

5. SOME PROPERTIES OF C, 37 

6. SOME PROPERTIES OF Z (CF. DEFINITION 3.6) 51 

7. SOLUTION OF EQ. (3-25) "VA'V T = 0" UNDER CONDITION 6.1 AND 

CONDITION 6.2 70 

8. GENERAL SOLUTION OF VA' V T = 91 

9. GENERAL SOLUTION OF VA' V T = IN APPLICATION OF BOOLEAN ALGEBRA . 101 
10. CONCLUSION . 106 






•in- 



1 . I NTKODUCTION 

In this paper, the number of most efficient binary codes and the 
construction methods are discussed in general, where the most efficient binaj 
codes mean codes with a minimum Hamming distance of p. 

The most efficient binary codes are defined mathematically as follows 



M(n,p) = 



11, X 12' x 13' 



x^. , x 



L ln 



x 21 , x 22 , x 23 , ..., x 2n 



, x. 



31' 32' 33' "" 3n 



(1.1) 



X -i » X„, X _, • . • , X 

, ml m2 m3 mn. 



Consider the matrix M(n,p), where (x.,iX.„,...,x. ) for 1 < i < m 

ll i2 in — — 

is an n digit binary code. Accordingly, x. . is 1 or and m is the number of 

■^- J 

most efficient binary codes. Here 



x., - x . , + x . ^ - x . ^ + . . . + x. -x. >p for any i f j; 1 < i, j < 
ll jl 1 ' i2 j2' ' in jn 1 - ^ J r d ' - ' J - 



m 



where p is the minimum Hamming distance. 

The purpose of this paper is to obtain maximum m and the value of 

each x. . . 
ij 

In Section 2, a theorem which plays an important role in the coding 
problem is discussed. 

In Section 3> the matrix H(n, p) (by which the coding problem can be 
discussed in general) is introduced, and general theory discussed. As a result, 
the coding problem is reduced to the problem of determining the independence of 
some vectors. 

In Section k, the characteristic values of H(n,p) are discussed. 



In Sections 5 and 6, some properties of the independence of vectors 
are discussed. 

In Section 7> solution under some conditions (group code condition 
implies these conditions; accordingly, group code is a special case of these 
conditions) is discussed. 

In Section 8, one method of general solution is discussed. 

In Section 9> Boolean algebra is used in finding a general solution, 

The c onclusion is stated in Section 10. 



2. A THEOREM WHICH PLAY J AN IMPORTANT ROLE IN THE CODJN') PROBL 

In this section a theorem which piays an important role in the coding 
problem is first described, followed by a discussion of a second, related 
theorem. 

Definition 2.1 . Exclusive-OR operation "©" between any non-negative integers. 

Let a, b be non-negative integers. Define a © b as follows: when 
a and b are expanded to binary form, i.e., 



a = a2 + a .,2 + . . . + a, 2 + a_ 
n n-1 1 



b = b 2 n + b ,2 n_1 + ... + b-,2 + b_ , 
n n-1 1 



n-1 



a © b = (a © b )2 + (a , © b , )2 + . . . + (a, © b, )2 + (a_ © b,J . 
n n n-1 n-1 1 1 



Here the symbol "©" of the right-hand side of the above formula is an exclusive- 
or operation in the usual meaning. 



Theorem 2.1. Let z~, z. , .... z , be real numbers. Consider the matrix 
7 1 n-1 



Z = 
n 



V V V ■"" Z N-1 



'l' V z 3' '"' z l©(N-l) 



'i> Z i©l' Z i©2' '"' Z i©(N-l) 



Z N-1' Z N-2' Z N-3' ""' Z 



where N = 2 and n > 1, 



-k- 



The matrix Z can be transformed to the diagonal matrix by the 



orthogonal matrix as follows 



where 



Z = U AU 
n n n 



1, 1 



Un V N \l, -I* 



'1, 1 



l1, "I, 



X . . . X 



'1, 1' 



a, -i- 



- (u ,u i; •••* u (n_ 1 )-) 



and 



A = 



: (N-1), 



Here, the symbol "x" means the direct product (Kronecker's product) and 



i, i\ A, i 



i, i 



k i, -I. 



X \ I X ... X 

^1, -1/ \h -1 



'1. 1 



means the n direct products of 

The following relations can also be obtained 



1, "I 



x. = -A (vV-"' z (n-i) )u i 



z i ■ ^ (x O' X l'"" X (N-l) )u i 



for any i, where < i < (N - 1). 



-5- 



Proof. Since the matrix Z is a symmetric real matrix, Z can be transformed 
n n 

to a diagonal matrix by an orthogonal matrix. When n ■ 1, Z, , U, are 

z - ■ V Zl 
V z o 



u ^vtC-J = (u °' Ul) 



respectively. The relation 



u ( X ° ° ) u = -± ( lr ) ( X ° ° ) -i I 1 ' ) = i f X ° + Xl ' X ° ' Xl 

1 \0 x 1 / X ^2 \1, -1/ \0 x 1 /^2 \1, -1/ 2 \x - x x , x Q + Xl 



holds. Therefore, letting 



z Q = | (x Q + xj_) = \ (x Q ,x 1 ) f j = j (x ,x 1 )u 



z i = I (x o - x i } = \ ( V x i } (J = ^ ( V x i )u i' 



the relations 



x Q = z Q + z ± = (z , Zl ) ( ^ j = nT 2 (z , Zl )u 



x i = z o - z i = ( V z i } (^J = ^ ( V z i )u i 

can he obtained. Therefore, the theorem holds for n = 1. 

Now suppose that xhe theorem holds for n, then it may be proved by 
mathematical induction that the theorem also holds for (n + l). 

It is possible to let 



-6- 



n+l 



x , x 1 

X l' x o 



where 



and 



X = Z 
n 



X l = 



V Z N+1' "••' Z 2N-1 



. N+1 , z N , . .., z le ( 2N _-L) 



J N+2' 



(2.1) 



The relation 



Z 2N-1' Z 2N-2' '"' Z N 



n+1 



1, 1 



J 2 (n+1) \ 1, -1 



I X . 



1, -1 



(n + 1) 



. X 



1, 1 



1, "I 



_1 
sT 2 



1 



1. 1 



U/^ \l, -1 
V 



1, 1\ /I, 1 

x...*[ 



n 



X 



1, "I 



.1, -1, 



_> 



1, 1> 



^2 ^ X \l, -1, 



, /U , U 
1 / n n 



^2 



U , -U 
n n 



(2.2) 



holds clearly. 

As the theorem holds for n from the assumption, 



-7- 



x n = u 

n 



\ 



N-l 



y. =A (z ,z 1 ,...,z N _ 1 )u. 



1 



'N 



r '^o ,J l' ••*"N-1 / '*I 



> 



(2.3) 



hold, where < i < (N - l). 

In Eq. (2.1), letting 



z . _ = z 

i©N i 



for < i < (N - 1), 



X n = 



'1* 



z l> z 0' 




> Z N-1 



Z N-1' Z N-2' 



"•' Z 1©(N-1) 



., K 



holds. Therefore applying the theorem to X, , 



X = U 

1 n 



y 



N+l 



U 



>v 



y 2N-l' 



y (2A) 



y n©i =</n ^i' z I"-- Z N-l )u i =VN ( VVl-' Z lH )u i 



1 Z n©i ~ ^ (y r y N+l^°^ y 2N-l )u i 



^ 



hold. 



Now, let 



-8- 



A, = 



> 



X (N-1) 



> 



(2.5) 



'N 



^N+l 



A. 



x 



2N-1 7 J 



such that 



^ 



I < A 1 + V = 



N-l 



> 



N 



N+l 



| (A,-A 2 ) 



(2.6) 







y 2N-l' 



Then from Eqs. (2.1) through (2.6), the relation 



-9- 



Un+1 \o a) Un+i 



, u u 

/ n n 

U -U 

n n 



A i ° 



*2 



u , u 

n n 

U , -U 
n n 



A l +A 2 

u — u , u 



A, ■ Ag 



U 



n 2 n n 2 n 



\~*2 



A l +A 2 

u , u — u 



n 2 n n 2 n 



X Q , X-j^ 

x x , x Q 



= z 



(n+1) 



holds. Therefore, 



A l ° 
(n+l) n+1 \ Q / n+1 n+ 



x 



Vi < 2 - 7 » 



x 



(2N-1), 



holds . 



From Eqs. (2.5) and (2.6), 



X i = y i + y N+l 



X N+1 == y i ~ y N+l 



hold, where < i < (N - 1). Therefore, from Eqs. (2.3) and (2.4), 



= n/n (V z l— Vl^i WN ( V Z N+l--- Z 2N-l )u i 



N ^ V z i>--> z N-r V z n+i' • • • ' z 2n-i ■ 



u. 



(2.8) 



■10- 



*N+i =/N ( W--- Z N-1 )U 1 -^ ( V Z N + l'-"' Z 2N-l )u i 



(u. 
1 
-u. 



(2.9) 



can be obtained, where < i < (N - l). Letting U . = (v , v,, . . . , V 2N _]_)^ 



N+l 



v. = 

l 



- r 1 

^2 \ u. 



> 



1 f U i 



N+l 



J"s 



•u. 



(2.10) 



holds, since 



i / U » U 

u i ="F n n 

n+1 ^2 V U , -U 

x n n 



/here < i < (N - l). Therefore, from Eqs. (2.8), (2.9), and (2.10), 



x 



x. =n/2N (z ,z 1 ,...,z 2N _ 1 )y. 



"\ 



} 



z ] v 

2N-1 ; N+i 



(2.11) 



can be obtained where < i < (N - l). 
From Eq. (2.11), the relation 



(W-'W =nS> ( W"-' z 2n-i )( V v i"-" v 2n-i ) 



= ^ (VV-' Z 2N-l )U n + l 



holds. Therefore the relation 



■ 11- 



( V Z 1--- Z 2N-1 ) = ^ ( V X r-'Vl )U r 1+ l 

v2N 



holds since U n U , = E , • where E . is the unit matrix of order n+1. 
n+1 n+1 n+1 n+1 

From Eq. (2.12), 



Z i ^ ( V X l^*^ X 2N-l )v i 



can be obtained, where < i < (2N - l). 

The above description has made it clear that the theorem holds for 
(n + 1). 



Theorem 2.2. In Theorem 2.1, 



T„ T 

u.Z = x.u. 

in li 



n T 

holds, where < i < (2 - l), and u. means the transposed matrix of u. 



Proof . From Theorem 2.1, 




x x u x l 



u T Z = u T U . |U = (0,... ,0,1,0,. ..,0) I . JU 

in\ . In I , /n 

/ \ ° ' 

X N-l/ \ X N-1> 




= (0, . . .,0,x.,0, . . . ,0)U = (x.u. _, x.u. ,,..., x.u. , v ) 
' ' ' i' ' 7 ' n l lO i ll l i(N-l) 



T 



x. (u.-.,u. ,, . , .,U. /„ ,\) = x.u. 
i lO ll i(N-l) l l 



can be obtained, since 



■12- 





T 



U n = (u ,u r ..., Vl ) = 



l N-l 



3. GENERAL THEORY OF MOST EFFICIENT CODES 

Definition 3-^- » 1 code 

Let i be a positive integer, ^ i < (2 - l), and let the binary 
expression of i be as follows: 



i = x. / x2 + ... + x.,2 + x._. 

i(n-l) ll iO 



The 



n, let the binary code (x. , 1 u...,x.,iX Jft ) be called "i" c 

i(n-l; ll iO 



ode 



Notation 3-1 . dist(i,j) 

Let the Hamming distance between i code and j code be expressed by 
dist(i, j). 

From Definition 2.1, Definition 3«1 and Notation 3«1.> 



dist(i, j) = i e j 



(3.1) 



clearly holds 



Definition 3.2. Matrix H(n, p) 



The matrix H(n, p) is a square matrix of order 2 and is defined as 



follows : 



00' 



h 0l' h 02' 



> h 



0(N-1) 



H(n,p) 



h 10' h ir h 12' ■•■' h l(N-l) 

h 20 , h 21 , h 22 , ..., h 2(N _ l} 



h (N-l)0' h (N-l)l' h (N-l)2, *' h (N-l)(N-l) / 



(3.2) 



-13- 



-1k- 



where N = 2 , n > p > 1. Here, 



h . = 1 when dist(i,j) < p 



h. . = when dist(i.j) > p 
ij - 



> 



From Notation 3»1> 



dist(i,j) = i©j=Oe(iej) = dist(0, i e j) 



holds. Therefore, 



(3.3) 



h . . = hu. / . . \ 
ij 0(i©j) 



(3A) 



can be obtained. 



Now, define h. as follows 
7 l 



h. = h n . 
l Oi 



(3-5) 



Then, 



h n = h. . 
li 



1 i,i©l 



lu = h. 



i,i« 



= h 



i©l,i 



h. 



1©2,1 



(3.6) 



^-1 " h i,ie(N-l) h ie(N-l),i 



can be obtained for any i (0 < i < N - l). Therefore, the matrix H(n,p) 
defined by Definition 3.2 can be expressed by 



■15- 



H(N,p) = 



h Q , h L , h 2 , 

h> V h y 



...,h 



le(N-l) 



V h iel' h ie2' ••" h ^ 



ie(N-l) 



(3-7) 



.V-l' \-2' ^-3' '■'> 



.., K 



where 



h = h. . = 1 
li 



(3-8) 



From Definition 3.2 and Eq. (3»6)> 



h o + h i + •'• + \-i = h io + h u + ••• + h i 



(N-l) 



= K(n,p) (3-9) 



can be obtained, where 



K(n,p) = C„ + C-. + ... + C 

v ,r n n 1 n p-1 



(3.10) 



Example 3 » 1 



H(n,l) = 



= E. 



K(n,l) = n C = 1 



Clearly, H(n, l) is a unit matrix of order N. 



Example 3*2 



Example 3 • 3 



H(n,n) = 



■16- 



K(n,n) = CL + O. + CL + . . . + C _ = 2 n - 1 
n n 1 n 2 n n-1 



H(3,2) = 




K(3,2) = 3 C Q + C^ = 1 + 3 = k 



Theorem 3-1 - The matrix H(n, p) can be transformed to a diagonal matrix by the 

orthogonal matrix U , that is, 

n' ' 



H(n,p) = UAU 
' n n 



and 



\ =Vn (VV-ViK 



hold, where 



-17- 



h i = ^ ( VV-Vi )u i 



A = 




\ ° 



N-l 



Proof . Applying Theorem 2.1 to H(n, p), the theorem clearly holds. 

Now, the most efficient coding condition is equivalent to the following 
condition: that is, to find a maximum m such that 



H = E 
m 



(3.11) 



where 



H o = 



ih~, h. . , h. ...... h. 

i,©i ' i-.©i ' i,©i 

12 13 1 m 



h i 2 ®V V 



h. .,..., h. . 
i_©i ' 1 ®i 

2 3 2 m 



h. . , h. . , h^, . . . , h. 

3 13 2 3 m 



(3-12) 



h . . , h . . , h . ...... h_ 

1 ©l-,' 1 ©1 ' 1 ©1 ' ' 

ml m 2 m 3 



and E is the unit matrix of order m. 
m 

Therefore, from Theorem 3-l> "the most efficient coding condition is 



also equivalent to the following condition: that is, there exist u. , u. , 

X l X 2 

u. for maximum m such that 

1 
m 



-18- 



H = 



U 



T 

u. 



A(u. ,u. , . . . ,u. ) = E 
1, 1 ' 1 m 

12 m 



(3-13) 



in) 



where 



u 



U n = (u 0)Ul ,...,u H ) = 



\u 



N-li 



that is, u., etc., means the transposed matrix of u., etc, 
Now, let 



V = 



(3.14) 



Then, Eq. (3-13) leads to 



m/ 



T 
VAV = E for maximum m. 

m 



(3.15) 



Asu. , u. , ..., u. are column vectors belonging to the orthogonal matrix U , 
1 1 1 2 1 m 



T 

W = E 



m 



(3.16) 



-19- 



can be obtained. Therefore, from Eqs. (3«i5) and (3.16), 



T T 

VAV = VV = 



tn 



.*. V(A - E N )V T = 



(3.17) 



can be obtained, where E is a unit matrix of order N and the right-hand side 
"0" of (3»17) means the zero matrix of order m (where every element is zero). 



Definition 3-3 » Define the vectors £„, C,, , ..., i , as follows 



V 



T 
u. 



' r„ ^o ;5 l"" ,& N-l^ 



>/n 



ml 



There exist m independent vectors among i , £ , ..., L since V 
consists of m row vectors belonging to the orthogonal matrix U . 

Therefore, as understood clearly from Eq. (3. 17) and Definition 3°3> 
the most efficient coding condition may be found by finding the solution of the 
following equation: 



(£ ,5 1 ,...,.£ b . 1 )(a - V«o' c i'-"'Vi ) = ° (3 - l8) 



such that the number of the independent vectors among ( £ n , £, , . . . , C ) becomes as 
large as possible. 



-20- 



Now, some relations which hold among i , £ , . .., C are described 



below. 



Definition ?>.k . Operation s 

Given two matrices A and B whose number of rows and columns are n 
and m respectively, i.e. 



' a ll' a l2' "*' a im' 



a 21 , a 22 , . .., a 2m 



A = 



and B = 



b lx , b 12 , ..., b lm 
b 21 , b 22 , ..., b 2m 



a,, a , . . . , a 

nl n2 



nm/ 



b .., b _, ...fti 

nl n2 nm 



Define A a B as follows 



' a ll b ll> a 12 b 12' "■'' a T- b 
^l^l' a 22 b 22' '"'' a ° mlD 



A b B 



a , b , , a _b _, . . . , a b 

nl nl' n2 n2 nm nm, 




Definition 3.5. |. 



Define | . as follows 
1 



Vn 



U = 



(l ,^ 



•'^N-l^ 



that is, l , |,, . .., I N are the column vectors of vN U . Accordingly, 



I . = VN u . 



(3.19) 



holds . 



-21- 



Theorem 3-2 



6 t«i = e t ■ h 



holds, for any t, i (0 < t, I < N - l) 



Proof. When n = 2, 



n u, -1, 



x 



1, 1 
1, -1 



1, 1, 1, 1 



1, -1, 1, -1 



1, 1, -1, -1 

1, -l, -1, 1 



0' 1' P' v 



holds. Therefore 



f 3- 




can he obtained. Therefore, the theorem holds for n = 2. 

Assume that the theorem holds for n. Then, by mathematical induction, 
the theorem also holds in the case (n + l). 



7 2 (n + l) y m J^ [ ^ 



2 n U, ^2 n U 
n n 



n+1 



1, -1 



sf^U , -^ 



(3.20) 



u 



n, 



holds, clearly. 

Since the theorem holds for v2 U by the assumption, the theorem 
clearly holds for 

r 



-22- 



Therefore, letting \l2^ n+1 ' 



U , be expressed by 



^^ ' U n + 1 = (VV-VrV-W^ (3.21) 



the theorem holds for 



2% 

n ) = 'VV-'Vi 1 

n. 



(3-22) 



Since 



and 



^u n = (i^,...,!^) 



J^ 



V2 n U. , N/2 n U 



U 



n+1 \ . O? 



^2 n U , W2 n U 
* n r 




(3.23) 



i-l 



holds. Therefore, 



■:']- 



W 




-5 



1 
-1 
■1 



= \» 



m \ m1 *i 



, -1 

holds where < I < N - 1. 

The above discussion has shown that the theorem holds for (n + l) 

Theorem 3-3 



^ = c t H H 



holds, for any t, I (0 < t, Z < N - l). 



Proof. The result is clear from Theorem 3.2 and Definition 3-3< 



Definition 3«6- z. 



Define z n , z, , z , . .., z , as follows: 



•4 z, = (1,1,...,1)L, 



that is, z. is ~r- multiplied by the sum of all elements of the vectors £ 
1 n/n 



Theorem 3»^ 



C t ' ; I ■ /H z tel 



for any t, I (0 < t, i < N - l) . 



■2k- 



Proof . 



#i 



= (1,1,. ...,!)(£ a (,«) = (1,1,...,1)L S (from Theorem 3.1) 



'£ 



f£ 



- z 



te£ 



(from Definition 3.5) 



From Definition 3-3 and Theorem 3«^> 



T 1 

V V = - 

N 



.T 
5 N-1 



(^ ^ 1 ,...^ N _ 1 ) - 



N 



C T C C T C C T C C T C 
b CTO' b b l' b S 2' '"' b O b N-l 

C T C C T C C T C C T C 



\ C T c C T c C T c C T c 

\ b N-lV b N-l b l' b N-l' b 2' *' b N-l b N-l ( 



_1 

nTn 



rz , z x , z 2 , 



-i /T\T * -1 



' Z N-1 



J l' V Z 3' "•' Z 1©(N-1) 



i' xel' ie2' "' i©(N-l) 



(3-21+) 



lZ N-l' Z N-2' Z W-3' "*' Z 



can he obtained . 

Now, following the preliminary discussion above, the most efficient 
coding condition is discussed below. 



Definition 3«6. Define A' ,\! as follows 



-25- 



/V 1 



A' = A - E N = 



V 1 







\ /* 



•(N-l) 



4 



/ 

- 1 ' \ S-i/ 



(cf. Theorem 3.1) 



Definition 3.7. Z 



Define Z as follows 



= n/n V V = 



'1' 2' 



z l> V 



V Z V 



'V 



' Z N-1 



••"' Z 1©(N-1) 
•"> Z 2©(N-1) 



Z N-1' Z N-2' Z N-3' °°°' Z 



From Eq„ (3«17) and Definition 3-6, 



VA'V T = 



(3o25) 



can be obtained. Therefore 



(V T V)A'(V T V) = 



(3.26) 



can be obtained. Conversely, from (3.26) and (3.16) 



V(V T V)A*(V T V)V T = 



VA'V T = 



can be obtained. Therefore, when W = E holds, the condition (3«25) is 



m 



equivalent to the condition (3.26) 



-26- 



From Eq. (3-26) and Definition 3.6, 



ZA'Z = 



(3-27) 



can be obtained. Therefore, to find the most efficient coding condition, find 
the maximum m such that 



W 1 = E 



> 



ZA'Z = 



(3.28) 



T T 

Theorem 3.5 . When VV = E and V V = Z, the rank of Z is m and the characteristic 

values of Z consist of "l" (m times) and "0" (N - m times). 



Proof. Since W = E holds, 

m ' 



det(\E - VV T ) = (X - l) m 
m 



can clearly be obtained. 

On the other hand, since 



holds generally, 



T T N-m 

det(\E„ - V V) = {det(\E - W )}X 
N m 



det(\E N - V T V) = (\ - l)^ (N - m) 



(3.29) 



can be obtained. 



T, 



Applying Theorem 2.1 to V V, 



/ °' 



Z = n/n V V = 



z . , z. 



-27- 



z l' ••" Z N-1 



., ^ iel , ..., - ie(N _ 1 ) 



Z N-1' Z N-2' •**' Z 



= U 



U 



x 



(N-l) 



(3-30) 



can be obtained. 

From Eqs. (3.29) and (3«30)> "the rank of Z is m and the characteristic 
values of Z, i.e., x„, x, , ..., x w _ 1 consist of "l" (m times) and "0" (N - m 
times) . 



k N-l 



From Theorem 3-5> finding the condition for the most efficient codes 
can also be reduced to finding the solution of equations 



T 

W = E 



m 



ZA'Z = J 



(3.31) 



with the maximum rank of Z. 



Remark 3.1. From (3. 30), 



-A (w- z N-i )u i 



can be obtained. If x. = x. = ... = x. =1 and the other x. = 0, i_, code, 

L, 1_ 1 1 1 

12 m 

i,. code, ..., i code are all of the most efficient codes. 
2 m 



h. CALCULATION AND SOME PROPERTIES OF EACH \. 



The value of each X. is given by the formula of Theorem 3-l> i.e., 



X. =nT N (h ,h 1 ,...,h N _ 1 )u. 



where each h. is decided uniquely by the value of n and p. 

Another method of calculating each X. and some properties of X. are 
discussed below. 



Theorem 4.1. p = 1 if and only if \„ = A., = ... = X„ , = 1, 
^ J 1 N-l 



Proof . If X = X = 



N 



, = 1, from Theorem 3«1* 



h i = ^ ( VV--ViK "z (1 ' 1 '-" 1)u i = 



Vn 



1 when i = 
when i / 



can be obtained. Therefore, 



H(n,p) = 



can be obtained. Therefore, p = 1. 
Conversely, if p = 1, 



h~ = 1, h. = for i / 
l ' 



can be obtained. Therefore, 



/. 



. = "/n (1,0,0, . ..,0)u. = 1 for any i (0 < i < N - l) 



Therefore, the theorem holds. 



-28- 



-29- 



Theorem 4.2 



\ Q + ^ + . . . + X N _ X = N 



^2 .2 

x + \ x + 



+ \ N _ ] _ = NK(n,p) 



Proof. From Theorem 3.1* 



+ \ 1+ ... + X N-1 =Vu (h ,h r ...,h N _ 1 )(u + u 1+ ... + Vl ) 



= ^N (VV— 'W 



nTn 





= Nh = N 



can be obtained. From Theorem 3-l> 



H(n,p) = U AU 
' n n 



2 2 

H = U AU 
n n 



X\ =^N (^^...^^^u. 



can be obtained, where 



ho \ 



H(n,p) s (^J^,...,^) = 



T 



T 
S-l 



Therefore, 



■30- 



,2 .2 
X + \ + 



+ Sli =n/n ^oVfe-fei^o + u i + ••• + Vi } 



= ^n (rg£ £^,. 



T 

Vn-i^ 



n/n 





= N£ J!, = N(h Q + 1^ + ... + hjj^) = NK(n,p) 



Theorem ^-.3 . The following relations hold: 

(1) \ Q = K(n,p) 

(2) Any \ for 1 < i < N - 1 are 



\ = K(n,p) > X = integer 



where the equality holds if and only if p = 1 



Proof. From Theorem 3«1; 



\ ± = VN (hQ,^, ...,h N _ 1 )u i = (h^h^ .. •^ h N _ 1 )i i = integer 



can be obtained, 



Since each h. is equal to 1 or 0, 



(h ,h 1 ,.„.,h N _ 1 )u > (h ,h 1 ,...,h N _ 1 )u. 



and 



\ = A (h ,h 1 ,...,h N _ 1 )u = h Q + 1^ + ... + hjj^ = K(n,p) 



-31- 



.*. K Q m K (n,p) > \. 



can be obtained. 

Suppose that there exists i, 1 <. i < (N - l), such that 



Then, 



x . v 



can be obtained, 
Since 



(V h l'---' h N-l )u O = 'Vl'-'Vl'"! 



(h ,h 1 ,...,h N _ 1 )(l - 5 .) =0 



n 



d - e ± ) - 



\ i 



i 

+ 1 
+ 1 

+ 1 



each element of (I - |.) is equal to 2 or 0, i.e., non-negative, and there 
exist elements except the first row element such that the value is equal to 2, 
(Clearly, there is no case except p = 1 for n = 1.) Therefore, 



(h ,h 1 ,...,h N _ 1 )(i - |.) = 



holds if and only if h =1, h, = h = 
p = 1. 



V: 



0. This is the case where 



-32- 



Theorem k.k 



where 



where 



X = X = ... = X 

12 n 

X = X =.....= X 

r +r r i +r o r i +r 

12 13 n-1 n 

X = \ = ... = X 

r, +r +r_ r, +r_+r, r ^+r , +r 

12 3 12 4 n-2 n-1 n 



X = X = ... = X 

r, +r +...+r . r,+r_+...+r +r r^+r.+.^+r 

1 2 n-1 1 2 n-2 n 2 3 n 



Q n-1 n-2 o 

r 1 = 2 , r 2 = 2 , . . . , r n = 2 = 1 , 



Proof. Consider any permutation of the correspondence 



X i(n-1)' X i(n-2)' ■•" x il' X i0 



>-. ^ X , jf . . ■ <, X . ^ x . 

1S (n-l) 1S (n-2) 1S 1 1S 



1 = x. / ,\2 + x. / „x2 + . . . + x.,2 + x. n 

i(n-l) i(n-2J il i0 



that is, any change of the column position of codes. 

From the definition of H(n,p), i.e., Definition 3-2, H(n,p) is 

invariant under this change. 

In H(n,p) = U AU , U is also invariant under this change. 
' n n' n 

Suppose that A becomes V under this change. Then, 



H(n,p) = U AU = U ^U 
7 n n n n 



holds. Therefore, 



-33- 

A = V 

can be obtained. Therefore, A has to be also invariant under this change 
As mentioned above, 



\ = X = . . . = \ 

12 n 

\ = \ = ... = \ 

r,+r_ r-,+r_ r , +r 

12 13 n-1 n 



\ = X = ... = \ 

r,+r^+ ..+r . r,+...+r +r r.+r,+...+r 

1 2 n-1 1 n-2 n 2 3 n 



must hold. 

Definition k.l . Extension of the definition of H(n, p) (cf., Definition 3-2) 

Define H(n,p) of the. matrix of order 2 where n < p and p = as 
follows 1 

a, 1, ~., 1' 
1, 1, ..., 1 

H(n, p) = I when n < p, 



1, 1, ..., 1 



'0, 0, . .., 



0, .0, ..., 

H(n,0) = when p = 0, 



.0, 0, ..., 0/ 



_ 3 4- 



Theorem 4.5 



H(n,p) = 



H(n-l,p), H(n-l,p-l) 
H(n-l,p-l), H(n-l,p) 



holds where n > 0, p > 0. 

Proof . It is clear from Definition 3-2 and Definition 4.1. 

Definition 4.2 . Extension of the definition K(n,p) (cf., (3-9)) 
In general, define K(n,p) as follows: 



K(n ' p) = n C + n C l + '•• + n C p-l 
K(n,p) = 2 n 



K(n,o) = 



when n > p > 1, 
when < n < p, 
when n > o, p = o, 



From Definition 4.2, 



K(n,n) =2 - 1 



K(o,p) =2=1 for p > o 



> 



J 



(*.l) 



can be obtained, 



Remark 4.1 . It is clear that the theorems, etc., presented until now also hold 
if the definitions of H(n,p) and K(n,p) are extended like Definitions 4.1 and 4.2, 

Theorem 4.6 



\ Q = K(n,p) 



X + X = 2K(n-l,p) 
1 



IV 



\_ + _C,\ + \ = 2 K(n-2,p) 

2 1 r, r -] +r p 



3 1 r x 3 2 ri +r 2 r ! +r 2 +r 3 



= 2 3 K(n-3,p) 



\~ + C,\ + C n \ +...+ C n \ + \ =2 K(n-s.p) 

sir, s 2 r,+r_ s s-1 r, +r^+...+r , r.+r^+...+r '*' 

1 12 12 s-1 12 s 



\„ + C\ + CLA. +...+ C n \ + \ 

■1 n2r i +r 2 n n_1 r l +r 2 + "- +r n-l 



n"n-l"r-, +r^+. . .+r *r n +r +. . . +r = 2TC(o, p) = 2 



holds. 



Proof, 



,U - , U . \ /A, \ / U 1 , U 

tt/ \ TT /\ TT 1 / n-1' n-1 \ / 1 \ n-1' n-1 
H(n,p) = UAU = - 

1 n-1 n-1 / \ ;2 ' \ n-1 n-1 



A l " A 2 
— - U ,, U n -~; — - U 



A, h Ag 



n-1 2 n-1' n-1 2 n-1 



A 1 - A 2 A 1 ■ + A 2 
^ U n-1 ~ 2 U n-1' U n-1 — 2 U n-1 / 



holds, where 



A = 



A l ° 



*B 



On the other hand, since 



H(n,p) = 



'H(n-l,p), H(n-l,p-i; 

^H(n-l,p-l), H(n-l,p) 



holds from Theorem k.5, 



-36- 

A- + iL 
H<n-l,p) = u n _ x — ^ U n-1 (4.2) 

can be obtained. Therefore, from Theorem 4.3 and Eq. (4.2), 



\ n + K 
r 

= K(n-l,p) 



\ Q + \ r = 2K(n-l,p) 



must hold, where r, = 2 



Similarly, since 

'H(n-2,p) H^^p-l)' 
H(n-l,p) = 

H(n-2,p-l), H(n-2,p) 



holds from Theorem 4.5, 



k n + X + \ + \ = 2 2 K(n-2,p) 

^ r 2 r x +r 2 



\„ + _C,\ + \ = 2 2 K(n-2,p) (4.4) 

2 1 r r +r v '*' y ' 



must hold since 



\ = \ 

r l r 2 

n-2 
holds from Theorem 4.4, where r = 2 

Similarly, in general, 

\_ + C..\ + CL\ +...+ C n \ + A. = 2 S K(n-s,p) 

sir, s 2 r, +r^, s s-1 r,+r^+...+r . r, +r^+...+r 

1 12 12 s-1 12 s 

can be obtained, where r. = 2 for 1 < i < n and 1 < s < n. 



Accordingly, this theorem holds. 



5. SOME PROPERTIES OF C 

An independent vector in £ , £ , . .., £ , is not determined uniquely, 
Therefore, independence is defined as follows. 

Definition 5.1 . Independence of the vector £. 

Let £. be called an independent vector of £_, £,, . .., £ -, when it 
satisfies the following condition: £. cannot be expressed as a linear combina- 
tion of £_, (L , .... £. -, , i.e., there do not exist a_, a,, ..., a. , such that 
1 l-l 1 l-l 

6 i = a 0^0 + a i C l + '•• + a i-l £ i-l' 



where a~, a,, ..., a. , are real numbers. 
1 l-l 



Definition 5.2 . Dependence of the vector of £. 

Let £. be called a dependent vector in £ , £ , ..., C , , when it 
satisfies the following condition: £. can be expressed as a linear combination 



of £_, £,, . ... £. -, , i.e., there exist a~, a,, ..., a. 
1 l-l 1 l- 



1 



such that 



5 i = a o^o + a A + ••' + a i-A-l' 



where a_, a,, ..., a. , are real numbers 
1 l-l 



Definition 5.3 . Generator of £_ , C, ..., C , 



Let £ Q , t^, £ 2 , C p, o.,, C 2. lDe called generators of £ Q , £ , 



b N-l 



Theorem 5.1 . When £. (0 < i < 2 S - l) is a dependent vector of C, L, «.., £ . . 

each of £ (n - 1 > t > s) is a dependent vector of C, , C, ..., L 

_. . U J- IN — -L 

2 +1 



■37- 



-38- 
Proof . Since £ . is a dependent vector, £. can be expressed by 

S i = a C + a l^l + ••• + a l-l C i-l 



where < i < (2 S - l). 



Therefore, 



h B e 2 t = (a o^o + a A + ••• + a i-A-i> E ^ t 



2*+l ° 2 t 1 2 t + l "- 1 2^(1-1) 



where 2 n_1 > 2 1 > 2 S 



Therefore, from Definition ^.2, £ is a dependent vector of £ , 

2 +i 



^1' •" , Vl' 



Theorem ^.2 . When a generator C, is a dependent vector of C, £ . .., t , every 

£ (0 < i < 2^ S+ ' - 1) is a dependent vector of C, C, . .., £ , . 

2 S +i U X W_1 

Proof. Since £ is a dependent vector of £_, C, .... C T , , £ can be 
pS ^ 0' l 7 N-l s 

expressed by 



C, = a n £ + a, £,+...+ a £ 

2 S ° ° ! 1 (2 S -1) (2 S -1) 



Therefore, 

£ » C. = (a n C + a.. L + ... + a £ ) s C. 

2 S X ° ° X X (2 S -1) (2 S -1) 

£ = a £. + a. L ,+...+ a £ 
2 S ei ° X 1 iel (2 S -1) ie(2 S -l) 

can be obtained. Since < i © j < (2 S - l) for < j < (2 S - l) holds, £ 

2 S +i 
is a dependent vector of £ , £ , ..., £ 



J9- 

Theorem 5.3 . When £ is a dependent vector ol' i, £ ..., £ N _-,> ^pi+1 is also 
a dependent vector. 

Proof. Since C_. is a dependent vector of £_, C , . ... L T ,, 
2i 1 N-l 

C 2i = Vo + & A + "' + a 2i-i rJ 2i-l 

.'. 5 2± ■ 5 X - (a^ + a^ + ... + ag.^^.^) * ^ 

can be obtained. Here since 

< j © 1 < 2i - 1 for < j < (2i - 1), 

can be obtained. Therefore, C . . is also a dependent vector of £., L, .... 

2i+l 1 

Vr 

In general, the following theorem holds as an extension of Theorem $.1 
and Theorem 5-2. 



Theorem 5.h. When £ is a dependent vector of C_. C, . ... L, , , 
s, s Sfl 0' l 7 N-l 

2 +2 +. . .+2 

S ^ 
b is also a dependent vector, for any i, < i < 2 -1 and 

S l S 2 S i 

2 +2 +...+2 +i 

s > S l > S 2 > ' ' * > S £ - lo 

Proof . Since £ is a dependent vector of £„. C, . .., C , 

s, s s « U J- IN - _L 

2 X +2 2 +2 ^ 



£ „ „ = a n^ + a C + o . . + a £ 

S S B/j 1 1 s s s, s s s, 

2 +2 %...+2 * 2 +2 +...+2 -1 2 +2 N-...+2 -1 

s s s/ 1 1 1 s s s p s s 2, 1 

2 -^2 d +...+2 * 2 +2 -rf-...+2 -1 2 +2 +...+2 -1 



can be obtained. Since 



-40- 



s l S P S R 
< j © i < 2 + 2 + ... + 2 -1 

holds f or < j < 2 + 2 ■ + . . . + 2 - 1 and for < i < 2 - 1, 

£ = a J, . + ...+ a £ 

s, s S/, u i s n s i s /> s r> i s ^ 

2 +2 2 +...+2 +i 2 °+2 +...+2 -1 (2 °+2 +2 -l)©i 

can be obtained, where the right-hand side is the linear combination of £_, £, , 

S S l S ^ 
2 +2 +...+2 -1 

Therefore, £ is a dependent vector of C n , C-, , • • • , L T -, ■ 

s, s . S| u 1 1M-1 

2 +2 +...+2 +i 

Theorem $.5 . When £ is an independent vector of £>„, C, . .., £ , , £. is also 
an independent vector for any i, 1 < i < (2 - l). 

Proof . Suppose that there exists a dependent vector £. of £ , £ , . .., £ , . 
Then 



h = a o^o + a A + ••' + VA-1 



can be obtained, where 1 < i < 2 - 1, 



Now, 



l /..s , \ . 11 l-l l-l /r ,s . \ . 

(2 -l)ei (2 -l)©i 



accordingly, 



C = a £ + a, £ + ... •+ a , S _ (5-1) 

(2 S -1) U (2 S -l)ei X l©(2 S -l)©i (i-l)e(2 S -l)ei 



holds. Since 



< j © (2 S - 1) © i < 2 - 1 



-Id 

holds for any j (0 < J <- 2 S - L) and for any i (1 < i < 2 S - l) and for 

j < (i - l), the right-hand side of Eq. (5-1) is a linear combination of some 

of t>~, £,;...;£ • Therefore, i becomes a dependent vector of C A , L, 

X (2 S -1) (2 S -1) 

•••> Vl' 

This contradicts the assumption of the theorem. Therefore, £. is also 

an independent vector of i , £ , ..., i . 



In general, the following theorem holds as an extension of Theorem 5- 5* 



Theorem 5.6 . When £ is an independent vector of ^ n , C, ..., 

S, S Sp (J 1 

2 +2 +...+2 -1 

C , , £ is also an independent vector for any i, where 

s-, > s > ... > S| > 1 and 1 < i < (2 - l) . 

Proof . Suppose that there exists the dependent vector £ 
of £ Q , i ± , ..., i^_ ± where 1 < i < 2 - 1. Then 

£ = a C + a i + ... 

s a s,n s 11 

2 +2 +...+2 U lj +i 

+ V 1 + 2 S2 + ... + 2^- 1 ) + i2V 2 + ... + 2^- 1 l(i-l) 



accordingly, 

^ s s s ) E ^ 2 = ( a ^o + ••* 
2 X +2 2 +...+2 ^ -l) +i (2 ^-l)©i 

+ a £ ) & t, 

2 Sl +...+2 S( ' e " l) + i 2 Sl +... + 2 S(i " l) + (i-l) (2 i -l)©i 

can be obtained. Therefore, 



-42- 



£ = a_£ + a. £ + . 

s s b- s f 1 So 

2 +2 +...+2 -1 (2 -l)©i 1©(2 -l)©i 



(5.2) 



+ a C, 

2 X +2 2 +...+2 ( ^ _l) +i {2 1 +...+2 S( ' e " l) + (i-l}©(2 S ' g -i; 



ei 



can be obtained. Since 



0<{2+2+...+2*+j)©(2-l)©i<(2+2+...+2-l) 



holds for any j < (i - 1), where 



0<j<2-l 



and 



l<i<2-l 



Therefore, the right-hand side of Eq. (5*2) is a linear combination of some of 

i~, £,,...,£ . Therefore, £ becomes a 

1 s s s, s s s. 

2 +2 +...+2 -2 2 +2 +...+2 -1 

dependent vector of £ , £ , . .., C N _-,_- 

This contradicts the assumption of this theorem. Therefore, 

£ is also an independent vector of £ , £ , ..., £ , . 

S-. s s« u 1 1M-J- 

2 +2 +...+2 -1 

Theorem 5.7. When £ , „ is a dependent vector of £_, C, ..., 

— L ^n-1 ^n-2 ^n-s 1 

2 +2 + . . . +2 

C T , , it can be expressed as a linear combination of £„, £ , £ , , 
N-l 0' p n-s n-s+1' 

£ , . . ., C » that is, 

3'2 n - S (2 S -2)2 n - S 

£ n = a ^^ + a, C + ... + a £ 

2 n - 1 + 2 n - 2 + ... + 2 n - S °° X 2 n " S (2 S -2) (2 S -2)2 n - S 






2 n " S 2 n_S+1 



3'2 



n-s 



a"" 1 + 2 n " 2 + ... +2 n - s = (2 s - ) 



.n-1 



,(n-s) 



(2 S - 2)2 



n-s 



where 1 < s < n. Accordingly 



C t o = a~£. + a,£ + a^£ +...+ a £ 

_n-l _n-2 ^n-s . i 1 „n-s . 2 ^ ~n-s . /„s \ /r ,s v^n-s . 
2 +2 +...+2 +i 2 +i 2-2 +i (2 -2) (2 -2)2 +1 



(5.3) 



n-s 



can be obtained for any i (0 < i < (2 - l)). 



Pro of. From Theorem 5.2, £ , _ is a dependent vector of £_, C, 

~n-l o n- 2 o n_ s . Cr 1' 

2 +2 + . . . +2 +i 



..., £ N _ X for any i (0 < i < (2 



n-s 



l)). Therefore, there exist at least 2 



n-s 



dependent vectors in £ , £ , ..„, C 

Now the generators in £^, £ > £ ■, » C > . . . * £ > 

2 n-s' S £ n-s + l' 3 . 2 n-s' V-s)2 n " S 

Since 



^O'^n-1' "'>*> n-s^ 



1 

1 

-1 

1 -1 
1 1 

1 
-1 




(n-s) 



1 -1 



-kk- 



the vectors C>~, i , £ 

n-s 
2 2 

quantum vectors 



, . . . , £ are constructed by the 2 

(2 S -2)2~ 



n-s 



ll\ 



and 



-i/ 



n 

Therefore, there exist at most = 2 independent vectors in £_, £ , 

' p n-s 7 P n_s 

C n, .... £ . Here, if and only if the number of elements of each 

n-B+1' ( 2 s -l)2 n - S 
^ is 2 , the number of the independent vectors is 2 . 



n-s 



From the description above, there exist at least 2 dependent vectors 

n ( n— s ) 
Therefore, the number of elements of each £ is equal to or less than 2 - 2 

Therefore, the number of independent vectors in £ , C , £ 



5 



,n-s 



0' J „n-s' J ^n-s+l' "*' 



is at most 



(2 S -1)2' 



,n-s 



= 2' 



1. 



On the other hand, the number of vectors of £_, £ , C -, » 

Cr p n_s p n-s+ - 1 - 

£ is 2 . Therefore, £ 

(2 S -l)2 n - S 



(2 S -l)2 n - S : ^2 n " 1 + 2 n - 2 + ... + 2 n - 2 



can be expressed 



as a linear combination of £_, C , C n * 

p n-s' n-s+1' 

Since 



(2-2)2 



n-s 



2 n -\ 2 n - 2 , 



, a"" 3 > i 



N n-s 



holds for any i (0 < i < (2 -. l)), the subscript of each £ of the right-hand 
side of Eq. (5.3) is between and (2 n ~ 2 + 2 n ~ 2 + ... + 2 n_S - l). Therefore, 



Eq. (5.3) holds. 



Theorem $.8 



r r 3 • r 
k k+1 3 k 



N-r -2r. N-r 
s k s 



N-l 



-• •- 



N-r -r. 
s k 



-45- 



When every £. for N-r - r u .5 i 5^" 1 - L '-> a dependent vector of 



(, , i , ..., £ , £„ can be expressed as a linear combination of (, , £ , 

s k k 

t , S3. , ..., £ N _ r _ 2 "here ^ > r > r R and ^ = 2 ' , r g = 2 E , 

(k+1) k s k 



o n ~ S 

..., r s = 2 , 



. , r = 2 , that is 



Vr -r. = a 0^0 + a l^r v + & 2^2-r v + '•• + a N-r a -2r,/r Vr -2r^ 
sk k k s k K s k 



Accordingly, 



5 (N-r -r n )+i ~ a 0^i + a l^r+i + °" + Vr -2r, /r Vr -2r +i 

x sk k skksk 



can be obtained for any i (0 < i < (r - l)) 



Proof o As in the proof of Theorem 5»7^ £ n j £ > ^ , ,, .., ^ 

r k k *' ^s "k 
are constructed by the quantum vectors 



N-r -2r, ? N-r -r, 



s ^k 



and 



each with r, elements. Therefore, the number of independent vectors in £_, £ .> 

2 n r k 

C„ , ..., C T is at most — . Further, if and only if the number of elements 

k k k ^n 

of each t, is 2 , the number of independent vectors in £_, £ » ...» (L, is — . 

0' r. N-r. r. 
k k k 

From the assumption of this theorem, the number of dependent vectors of 



£-., £-, , ..., C„ -, is at least r + r. . Therefore, the number of elements of each 
1 ' N-l s k 

£ is not more than N-r - r, . Therefore, the number of independent vectors in 

N-r-r /N-r \ 

£~, i , (L , . . ., C T is not more than = - 1 1 . 

r. 2-r/ N-r, r. \ r. / 

k k k k < \ k / 



-k6- 



On the other hand, the number of £_, £ , £_ , .... £„ is 

r. 2r. N-r -r, 
N - r k k s k 



5 



Therefore, C, can be expressed as a linear combination of 



r n ' N-r -r, 

k s k 

b 0' V ' b 2r, ' "' b N-r -2r 
k k s k 

Since 



r l' V '"" V ■"' r k > 1 £ ° 



holds for any i (0 < i < (r -i))> the subscript of each £ of the right-hand 

i£— J- 

side of Eq. (5.^) is between and (n-r - r - l). Therefore, Eq. (5°^) holds, 

S K. 



Theorem 5°9 « Let n p,^ n n > n -> ■••* n / \ be as follows: 

u 1 2 / (n-k;_^s 

n n : the number of independent vectors of £_, C, . „., ^ TJ _-, 

in C , C £,...,£ 

° 1 ^ (2-1) 

n, : the number of independent vectors of £_, C, ..,, ^• M _-, 
2 k 2+1 2+2 2 U+lj -l 



n 



: the number of independent vectors of £ , £ , . .., £ , 

in ^(* + D< S 2 u + D +1 ' 5 2 (k + D +2 ' •••' ^.^ 

l / , \ : the number of independent vectors of £_, £, , ..., L T n 
/ 2 (n-k)_ 1 x 1 N-l 

N-2* N-2 +1 W 



Then 



n_ > n n > n > . . . > n / ,\ > 

- 1 - 2 - - ( 2 ^ ^-1) ~ 



holds, where < k < n - 1, 



Proof. It is clear. 



-U7- • 

Theorem '■> . LP . Rearrange the generators £ , £., £ , ^ ,., . .., £ n _ L of £ C, 

..., £„ in the order. (, , £ , L £ p , ..., £ p . Then the order of vectors 

after £ becomes: . ... £ ~» £ n <>> ^ ^ > £ i ^ > ^ ^ > 

n-P n-2 n-1 n-2 n-2 n-1 n-2 n-2 

2 2 2 +2 2 +1 2 +2 +1 2 +2 

^ n-1 n-2 ' ''■' n-2 ' n ' ^ n-1 ' ^ n ' 
2 n +2 +2 2 -2 2-2 2 -1 2-1 

Proof . The vectors after C, in £ , Q , . . . , C have always the factor 

2 " in their subscripts and have any combination from 2 ,2 , ..., 2, 1 

in their subscripts. Therefore, applying the substitution: 

0, 1, 2, 2 2 , ..., 2 n " 2 , S"" 1 

A a"" 1 , i, a 1 , ..., s n -3, 2 Q - 2 

, , r n-1 

to the generators of C, C, . .., L T -, , the vectors after the 2 th have always 

n-2 n-1 

the factor 2 in their subscripts and have any combination from 2 , 1, 2, 

2 , ..., 2 in their subscripts. That is, all vectors after the 2 th from 

^n-2 t0 ^gCn-D.-g ^ ^ V" 1 ^' 2 ^ ^ ^ ^ &1 ' "'" ^ ^ 

arranged in the new arrangement. The adjacent vectors 

^2 n - 1 + f(2 n - 2 ,2 n " 3 , . . .,£) V^f (2 n " 2 ,2 n - 3 , . . .,2 1 ) + 1 

in £ n , £, , ..., ^ TVT _-| (where f (2 I ,2 ,...,2 ) means that some combination 

n-2 n-? 1 
from 2 ,2 , ..., 2 is added) become respectively the adjacent vectors 

V" 2 + f (2 n - 3 ,2 n "\ . . .,2,1)' V" 2 + f (2 n - 3 ,2 n "\ . ..,2 } ±) + 2 n - 1 

after the substitution. 

Therefore, this theorem holds. 



-1*8- 

Example 5 . 1 

0, 1, 2, 3, h, 5, 6, 7 , 8, 9, 10, 11, 12, 13, H*, 15 , 
is rearranged to 

0, 8, 1, 9, 2, 10, 3, 11, 1*, 12 , 3, 13 , 6, H* , 7, 13 , 
after the substitution. 

Theorem 5-H- 



r 

N-2r N-r 
s - s 



dependent 
A 



V ^l 



V 



independent 



N-r -r N-l 
s k 



When every £. for N-r - r < i < N - 1 is an independent vector of 

1 S iC 

L, £, , . .., ^t\t -i an< ^ the others are independent vectors of £_., C, ..., £,, -, , 

where r, > r > r. , let C T and £, T be expressed by 
1 s k N-r N-r -r. 

s s k 

C T = a n ^ n + a, £ +a C + ... + a £ o (5-5) 

N ' r s ° ° X r s 2 2-r s (2 ^_ 2) (2 s_ 2)r ^ 



s 



(cf. Theorem 5 .7) and 



L, = b n £- + 13,5 + b C + ... + b . r (5.6) 

N " r " r k ° ° 1 r k 2 2-r N-r -2r, /r. N-r -2r 

SK K K skKsk 



(cf. Theorem 5.8). Then 



a. | = 1 for any i (0 < i < (2 - s)) 

N-r - 2r 

b. | = 1 for any i (0 < i < ) 

l — — r. 

k 



Proof. From the assumption of this theorem, £. for N-r -r<i<N-l 

1 S K 

is a dependent vector of ± , £., . .., £ . Therefore, of course, £ for 

N-r < i < N - 1 is a dependent vector. Therefore, from Theorem 5-7> Eq. (5-5) 
s — — 

holds. 

From Eq. (5-5), 

( Vr } * ( Vr } = a oVs + a l^r *(N-r ) + "' 
s s s s 

accordingly, 

^0 = a oVr + a l^r ©(N-r ) + '" (5 ' ?) 

s s s 



Substituting £ of Eq. (5-5) to Eq. (5-7), 

s 



2 
C = a (a n L + a £ + . . „ } + a n £ /„ \ + .... = a C + a at + 
000 1 r lr ©(N-r ) 1 r 

s s s s 



(a* - i)£ Q + a a^ r + ... = (5.8) 

s 



can be obtained, 



In Eq. (5-8), the subscript of each £ in each term of Eq. (5-8) consists 

of r , 2r , .... (2 S - l)r since i • r ©(N-r)<N-r for 1 < i < (2 S -2)r , 
s' s' ' s s s s - — s 

Therefore, from the assumption, those £ are independent vectors of £_, £,, ..., 
£ -. . Therefore, in order to let Eq. (5.8) hold, each coefficient must become 
zero. Therefore, 

a o = x 

Similarly 

a 2 - 1 

1 



-50- 

can be obtained. And, similarly, 



b 2 = i 

1 



can be obtained, 



6. SOME PROPERTIES OF Z (CF. DEFINITION 3.6) 
Suppose the following: 

Condition 6.1 . The independent vectors of C, £-, , £ p , • ••> £ N -, are only i , 
i v ..., 5 (k . l} , 5 (k . l} , ..., £ (k . l} ; and 5 ± for any i ( 2 k " + £ + 1 

2 2 +-L 2 +# 

(k-l) 
< i < N - l) is a dependent vector of £,_, i , ..., L -, , where < i < 2 



Define V , V, , V_, . . . , V , , x as follows 
1 2 (n-k; 



V, 



V. 



tt Q , 



^k> 



- (5 



2-2 



k' 



S l' 



& k ' 
2+1 



3 k ' 
2-2+1 



' £ k } 
2-1 



A 



.., £ 



gCk+D.! 



> (6.1) 



.... 5 



3-2 k -l 



V 2 (n_k) -1 ' (C (2 (n - k) -l)2*' ^2 (n - k) -l)2 k ' "" ^^ 



Definition 6.1 . Z. (cf. Definition 3.7) 

Define Z_, Z n , Z^, .... Z , , \ as follows 
0' 1' 2' (2^-1) 



12 



.k' 



k > 

1-2+1 



' k 
(1+1)2-1 



Z. = 

1 



k > 

12+1 



z k , 
\ 12 k ej 



(i-2 +1)< 



{(i+l)2 k -l}- 



(1+1)2-1 



k > "' 



i2 



Accordingly, 



-51- 



UNIVERSITY OF 
ILLINOIS LIBRARY 



■52- 



Z = 



V 



V 



z i' z 2' -' z (2 (^).x) 

V Z3 ' "" W^-l) 



Z iel> Z i»2' ••- ^(n-k)^. 



(2^-1)' "" 



Theorem 6.1 . Under Condition 6.1, 



2 2 

z o = z i 



2 2 

Z (2 (n " k) -1} := Vn Z ° 



z. • z. = — z. 

1 J nTn 1( 



holds, where of course < i, j < (2 -1} . 



V_ 



Proof . Since the independent vectors of C, , L, . .., L are only in , 
under Condition 6.1, 



T T 

V V = V V = 
11 



• = V , , , V T , . v =2^ 
(2 (n-k)_ l} (2 (n-k)_ l} 



(6.2) 



can be obtained (cf. Eq. (3.16)). 

The following relations hold clearly from Definition 3.5, 
Definition 3.7 and Definition 6.1, that is, 



-53- 



I T 

— v:v. 



■± v T v. , 



-i v T v 
Vn i ie2 



^ 



1 T 

= — v: ,v. 
/.. i©i i 



4 N le2 l 



> (6.3) 



IT IT 

V n - k) -l} = Vn ViV ie{2 (n - k) -l} ^ Vn V ie{2 (n - k) -l} Vi 



for any i (0 < i < 2^ n_k ' - l). 

Therefore, from Eqs„ (6„3)> 



Z 2 = — V T V n — V^V. = i V T V n V^V. = i V T (2 k E )V. (from Eq. (6.2)) 
l r i T i NiOOi N l x m ; i v ^ ^ ' ' 



k k 

|- -A Z A (from Eqs. (6.3)) = y- Z Q 



N 



Therefore, 



2 2 

z o - z i = 



= z ^).rl Zo 



can be obtained. From Eqs. (6.3), 



Z.Z. 
1 J 



IT IT ITT 

^ l0 s[ N ° J N 1 j 



i V T (2 k E )V. (from Eq. (6.2) 
N 1 m j 



2 k T 
— V V 
N i j 



= ^r: n/n Z. . (from Eqs. (6.3)) = — Z. 
N i©j ^ i< 



can be obtained, 



-54- 



Theorem 6.2 . Under Condition 6.1, any V. for 1 < i < {2^ n_k ' - 1} 
expressed by 



can be 



and 



V. = V n A. 
l l 



v o = Vi> 



V. = V.A. 
l li 



can be obtained where 



A = 

l 



*j_y a 2 : 



0' 



V a j©i' •••' 



(2 k -l) 



(2 k -l) 
le(2 k -l) 



>(2 -1) 



= U, 



a 



Oi 



a 



li 



Q 



2i 



a 



u 



(2 k -l): 



U k = 



'I, 1 

.1, -1 

v 



X 



% 1 



X . . . X 



(The number of 



.1, "I, 



X i 

.1, -1, 

y 



is k. ) 



Proof. Since every column vector, i.e., £ in V. is a dependent vector of £ , 

^1* "*f ^N-l frorri Condition 6.1, £ e V. can be expressed as a linear combina- 

i2 
tion of C, , £ , . .., C ,_ , i.e, 



'0' =T 



2 k -l' 



^ k = a^ + a^ + . . . + a^ S^ 



(6.4) 



Therefore, 



-55- 



(5 k ) « £j = (a C + a^ + ... + ^J^J ■ ^j 



accordingly 



^ k = a (vM + a Aei + ••• + a k ^ k , 

12 +j ° J X iej 2-1 (2-1 )®j 



(6.5) 



can be obtained for any j (0 < j < 2 - l), where the right-hand side of (6.5) 

is a linear combination of £ , £ , . .., £ . Therefore, 

° X 2-1 



12* 12+1 



12 +(2-1) ° 1 



' 6 k } 

2-1 



l 0' <V 



l 0' 



a , . . . , a 

* 2-1 



le 



(^-1) 



Accordingly, 



a , a , . . ., 

2-1 2-2 



V. = V_A. 
1 1 



(6.6) 



can be obtained. 



Applying Theorem 2.1 to A., 



A. = II A. II 
1 k 1 k 



can be obtained. 

From Eq. (6.h), 



«. 2k ) * ? 2 k ■ ^0 + a A + ••• + V-iW B V 



Accordingly, 



C . = a~£ , + a, 5 , + . . . + a .. £ . . 
1 ° 2 k 1 2 k +l 2 k -l 2 k +(2 k -l) 



-56- 
can be obtained. Therefore, similarly, 



^5i--W'VW""H ,ii 



V Q = V.A. (6.7) 



can be obtained. Therefore, from Eq. (6.6) and Eq. (6.7), 



V. = V.A 2 
l li 



and 



2 
V = V A 
i 



can be obtained, 



Theorem 6.3 . Under Condition 6.1, every V i for l<i< (2 ln -l) can be 
expressed by 



V. = V n A. 
1 1 



from Theorem 6.2. Then, 



A. . = A. -A. 



can be obtained, 



Proof. oiiuv 



-57- 



^ 



V. = V n A. 

1 1 



V. = V n A. > 

J J ( 



V. . = V n A. . 
i©j i©j 



(6.8) 



T T 

V V = V V A. 

i 00 



T T 

V V = V V A 



can be obtained. Therefore, from Eqs. (6. 3), 



"A 



Z. = Z n A. 
l l 



Z. = Z.A. 
J j 



(6.9) 



can be obtained. From Eqs. (6.9) and Theorem 6.1, 



■s/k „ „ n/n 



Vn 



i.j 2 T z i z j " ^ ViV; " J \\\\\\\\\\^\ 






= -f U.A„ A.A.A- U. = -f U. AT A.A.U. = ■— Z^A.A. = Z_A.A. 
.j^ n k k k ^ n 1 j k o k0ij Oij 



2 1 



(6.10) 



where 



Z = U k A Z Q U k 



A. = U.A.U. 
1 k 1 k 



A. = U.A.U. 
J k j k 



T 
V_V. . 
lej 



" v oVi A j 



-58- 



T 
i©j 



T 
V V V A A 

OOOi j 



2^ V. . = 2^ V A. A. (from Eq. (6.2)) 
m lej m o l j 



V. . = V_A.A. 
iej i j 



(6.11) 



can be obtained. Then from Eq. (6.8) and Eq. (6.11), put 



A. . = A. ' A. 



Theorem G.h. Under Condition 6.1, 



can be obtained, where 



a. . = 1 or -1 or 



V. = V Q A for any i (l < i < 2^"^ - l) 



Q 



Oi 



A. = U, 
i k 



a 



li 



a 



(2 k -l)i 



Without loss of generality, put 



a. . = 1 or -1 



Accordingly, 



2 2 
A = A = 
A l A 2 



+ A' 



{2 (n ' k) -l} 



= E, 



of. From Theorem 6.2, 



Accordingly, 



•59- 



v o = Vi 



T T 
V V = V V A 
i 



Z " Z A i 



(from Eqs. (6.3)) 



(6.12) 



can be obtained, 



Let Z-., A. be 
0' 1 



*\ 



z o = U k 



u. 



2 k -l 



and 



> 



(6.13) 



o: 



Oi 



A. = U. 
1 k 



a n . 
li 



u 



a 



2 k -l)i; 



J 



From (6.12) and (6.I3), 



v. = v.a. . 



v. (a.. - 1) = 



(6.14) 



■6o- 



can "be obtained. From (6.14), 



V. = 

J 



or a . . = 1 



a. . = + 1 



(6.15) 



can be obtained. 

Therefore, from Eq. (6.15) and the relation of Theorem 6.1, i.e., 



2 2 2 2 

i'-^i^-u'Tx ° 



a.. = 1 can "be determined without loss of generality for any value of V. 



Theorem 6.5 . The absolute value of characteristic values of Z. for any i 

(0 < i < 2^ n_k ^ - 1) is equal to or —- . 

VN 

Proof . Applying Theorem 2.1 to Z , 



z o = \ 







u. 



2 k -l 



/ 



can be obtained. 
Since 



holds from Theorem 6.1, 



2 2 

z °^ z ° 



2 2 
V. = — V. 

1 4k x 



can be obtained. 

Therefore, since 






v.(v. - z- ) = o 

1 L s/N 



v. = or V. = — 

1 n/n 



2 2 

z o ■ z i ■ • 



2 2^ 

= Z {2 (n - k) -l} = N/N Z ° 



holds from Theorem 6.1, the absolute value of characteristic values of Z. for 

, i 

Cn-k) ? 

any i (0 < i < 2 V ' - l) is equal to or — . 

VN 



Theorem 6.6. When 



/% 



V. = V_A. = V U 
J j Ok 



a 



1J 







Q 



(2 k -Dj 



n-k 



for any j (l < j < 2 - l) under Condition 6.1, if 



(4 n) ) T 



e v 



and 



V 



I = S2 + i 



j 



holds, where < S < 2^ n ~ k ' - 1 and < i < (2 k - l), 



•62- 



(l^.a^-.a e(a ^ ) - (4 n " k) ) T 



holds where 



u = fu (n) u (n) J n) ) =-i (V n > a (n) e (n)> ) 



cf. Definition 3.5, 



Proof. Since 



(°)V e V 



(4 B) ) 



I = S2 k + i 



holds from the assumption 

f| D) ) T =(W f). (4 n " k) ) T (6.16) 

can clearly be obtained. Therefore, 

v . (^ 

holds . 

Let the ith row vector of V. be v. 

J 1 

Since 



V. = V n A. 



'1 ^S 



can be obtained. Therefore, from Theorem 2.2, 






/ (k)\T A / (k)Vr 
v. = in. J A. = a. . I u. ' J 



can be obtained. Therefore, 



fu (n) \ T - ^u (k)T a u (k)T a u (k)T a u (k) 
V U I ) ~ \^i ' a il u i > a i2 u i "•"' ^(n-k)^ u i 



T 



( (k) T (k) T (k) T \ , n 
= u ,u. ,...,u. a (i,a.,,a. n , . . .,a , , \ 
\ i i i / ' il' i2' ' i(2^ n '^-1) 



(6.17) 



can be obtained. Therefore, from Eq (6.16) and Eq, (6.17), 



il' i2' i(2^ ^-1' 



(4 n " k) ) 



can be obtained. 



Condition 6.2 . Suppose that there exists £. for a suitable i (0 < i < 2 - l) 
corresponding to A. for any j (l < j < 2 - l) such that 

J 



CI 

Oj 



a 



(k) _ 



lj 



a 



2j 



a 



(2 k -l)j 



where 



-6k- 



A. = U, 
J k 



Q 



Oj 



\ 



a io ° 



a 



2j 



a 



(2 k -l)j 



(cf . Theorem 6.2). 



Theorem 6.7 . Let A. be 



a i' V •••' a , k 



(2^-1) 



«!, 



A. = 
J 



a , a , . . ., a 

J le(2 -1) 



'*' ^' '•" ^(2 k -l) 



(2 k -l) 



• • • :. a Q 



and 



Under Condition 6.2, 



a=a=...=a. ,=a. n =...=a . =0 

o i i-i 1+ i (2 k_ 1} 



a. = 1 
l 



can he obtained. 



-65- 



Proof . Ap] g Theorem 2.1 to A. 

J 



a - -±- (a a a )u (k) - -A- ^ (k) Vu (k) - fu (k) Y r u (k) 



^ J° J 1 j(2 
can be obtained. Therefore, 



&n = 1 when £ = i 
a.g = when £ ^ i 

can be obtained, 

Now, in the case of a group code, it is found below that Condition 6.1 

and Condition 6.2 are satisfied., 

(n) T (n) T 
In a group code, if there exist row vectors of V in ui. , u , ..., 

( n ) J ■ ( n ) ( n ) ( n ) +^ ^ ^ 4- * 

u / , N and xn u / , \, u / , \ , . .., u. T ' , the number of row vectors of 
2 (n~l)_ 1 2 (n-l)' 2 (n-l) +1 ' TJ-1 

(n) (n) ( n) * 
V in ul , u, ..... u , , \ is equal to the number of row vectors of V 
1 2^-1 

. (n) T (n) T (n)' 1 ' 

inU 2 (n-l)> U 2 (n-1) + ^ — Vl ■ T 

Similarly, in a group code, if there exist row vectors V in u^ , 

f \? ( > T " '■ \ T ( \ T f \ T 

(n) \ n ) ^ • l n ) l n ) ( n ) 

\x: , .c., u . ana xn u , u , ..„, u , , \ , the number of row vectors 

1 2-1 2 k 2+1 2 U j -l 

( i ( i f > 
of V in u. , v.: ..-.., u \ is equal to the number of row vectors of V 
1 2 k_ x 

(n) T (n^ T (n) T 
in u . , u . , .... u /. , \ . Therefore, if there exist any independent 

2 k 2 k +l 2 (k+l) -l 

vectors of £ , L ,...,£ 'in £,£,..., £ , and in £ , 

U 1 W_1 £2 £2+1 (£+1)2-1 (£+1)2* 

£ , , . .., £ , , the number of independent vectors of £_, C, „.., 
(£+1)2+1 (£+2)2-1 ° X 

E_ , in £ v ; 5 v j ..., 5 , is equal to the number of independent 
W_1 i2 K £2+1 (£+1)2-1 

vectors of C, t, „„„, C in £ , C ,...,£ fc . 

U X W 1 (£+1)2* (£+1)2+1 (£+2)2-1 



-66- 



Therefore, since the total number of group codes is of the form 2 , 
if there exist independent vectors of £ , £ , . .., C in £ , £ , . .., £ , 

t ~ 

the number of independent vectors is of the form 2 (t < s). Therefore, 

applying Theorem 5-10 a suitable number of times to £_, £, , . .., L and 

renumbering the subscripts in natural order from the first vector, only £_, C , 

£„, . ... £ are independent vectors of £_, £, , .... C T .. and the others are 
2 / s -, \ 1 N-l 

dependent vectors of £~, £ , ..., £ -, . This is Condition 6.1. 

Now, consider uj , u' , u t where 
a b c 



"N 



I = S 2 + a 
a a 



K = S . 2S + * f 



I = S 2 + c 

C C y 



(6.18) 



and < S , S, , S < (2^ n_S ' ) - l), < a, b, c < (2 S - l] 

3, D C 

Assume that 



b c 



(6.19) 



holds. (There always exists I such that I ©1=1 is a group code.) 
Therefore, from Eq. (6.18) and Eq. (6.I9), 



S 2 S + c = (S © Sj2 + (a © b) 
c a b 



• • o — o © o_ 
cab 



c = a © b 



"\ 



> 



(6.20) 



y 



can be obtained. 






Applying The ore i: 6.1 bo Eq. 6.20, 



.(n-s) < p(n-s) _ ^(n-s) m ^(n-s) 



'S ®S, S 
a b a 



(6.21) 



can be obtained. 

Now, ui ' € V can be assumed without, loss of generality. Therefore, 
Eq. (6.21) means that Condition 6.2 is satisfied. 

Remark 6.1 . In the case that Condition 6,1 and Condition 6.2 are satisfied but 
the code is not a group code, 



S = S © S,_ 
cab 



is satisfied but 



c ^ a © b 



holds (cf. Eq. (6.20) 



Remark 6,2. When V satisifes Condition 6,1 and Condition 6.2, and 



% 



a 



(k) = 
i 



lj 



:t 



2j 



a 



(2 k -i)j 



holds (cf. Condition 6.2), 



[a 0J ,a lri ,a 2J ,...,a } 



-68- 

becomes an Abelian group under the operation of multiplication. Accordingly, 
considering the matrix a 



1, X, 



1, 



1, ..., 1 



a = 



1, a 1±f a ±2 , 



1> ^l' Q 22' 



a iV '••' a n-k) 
13 l(2 n kj -l) 



Q 



a 



S3' ••" 2(2^).^ 



l, a k , a k 

(2-1)1 (2-1)2 



. . ., a 



*-i)(2 (n - k) -i) 



(as u^ e V can be assumed without loss of generality, it may follow that 



01 02 

that 



= a 



o( 2 (n - k) -i: 



= l) there exist i_, i , . .., i / , \ such 



(2' 



•) 



,(k) (k) (k) (k) 

1 2 {2 ( n - k) -l} 



from Condition 6.2. 

From Theorem 6.6 and Condition 6.2, Ct is reduced to the following 
form: 



a 



(n-k) 
'0 

(n-k) 



T 



(n-k) 



T 



(6.22) 




-6 9 - 



Since {1,Q. .,&,..„,., a ) is an Abelian group as mi i<;d abo 

U 2j (2 k_ i} . 



f, (n-k) (n-k) 



p(n-k) 

" S k 
2-1 



becomes an Abelian group under the operation "h 1 



7. SOLUTION OF EQ. (3=25) "VA'V T = 0" UNDER CONDITION 6.1 and CONDITION 6.2 
Even if generators of £ n , £,, , .., £ , are rearranged in any order, 

m 

Eq. (3-25), i.e., VA'V" 1 " = 0, holds. Let the transformation of the rearrangement 
of generators of £ n , £, , . „., C be t, that is, 

V'T = W 

From Theorem 4.U, A' is invariant under the transformation, i.e., 

tA*t T = A' 

Therefore, 

WA*W T = VTA'T T V T = VA'V T = (7.1) 

can be obtained. 

T 
Since it is clear that A. = A. holds from Theorem 6„3> 

11 

VA>V T = (V ,V A 1 ,V A e ,...,V oA(2(n . k) ^ i )A-(y o ,V A 1 ,.„. ) V A [2(n _ k) ^) T 



" V A + VA + V2 A 2 + -• + A (2 (^). 1) A [2 (n-k). 1 , A {2 (n- k )_ 1) > V " ° 



Accordingly, 

V (A + A AAl + A 2V2 + ... + \ 2 (n-*)_ 1) \ 2 (n-K)_ 1) \ 2 (n-K)_ 1] »0 



)V* = 



(7.2) 



can be obtained, where 



-70- 



where 






A) 



A, 



A' a 






A 



2 (n " k) -l} 



Considering Theorem 6.7, let A. for any j (l < j < 2 - l) be 



V V ••" a 2 k_ x 



. i©l . /^k 



i©(2 -1) 



> (7A) 



a o ~ a i 



a , , . „ . , a 
2-1 ° 



i.-l i.+l n k , 
J J 2-1 



a. = 1 
i . 
J 



J 



< i. < 2 - 1 
- J - 



(7 = 5) 



Since 



\' 



J2 



A. 
J 



X ' k 
J2%1 



X ' k k 
J2 +2-1 



holds from Eq. (7=3), 



-72- 



V k 
J2 +i. 



A.' 



A.A.A. = 
J J 



j2 +(l©i ) 

J 



(7.6) 



\' 



[j2 k + i? k -l)©i 



can be obtained from Eq„ (7°*0 
Therefore, let 



A n + AAA + ... + A f x A / . v A , . x 
1 1 ( 2 (n - k) -l) {2 (n - k) -l} {2 (n - k) -l} 



The following relations can be obtained: 



(2 k -l) 
(7,7) 



° ° 2 k + i x 2.2 k + i 2 3 '2 k + i 3 



+ ... + \' 



In general, 



(2 (n-k)_ 1)2 k + . 



> 



i2 (n - k) -l} 



v . = \ \ + \ ' + ^'v + . . . + \ • / . * . y 

3 2%(jei ) 2 <2 k + (jei) {2 (n - kj -l)2 k + { jei , . , } 

^ {2 U_k; -l} 



where 



< j < (2 K - 1) 



y 



(7.8) 



-73- 

Now, the solution such that the number of most efficient codes if; 
is discussed below. 



Theorem 7.1 . In Eq. (7-8), when V Q = 0, 



(7.9) 



V. = 
J 



can be obtained for any j (0 < j < (2 -l)) 



Proof. Applying the result of Theorem 3.1 to Eq. (7-8), 






in) (n) (n) 

(h^h i; . ..^(u + ay 4- ... + a , 

+1 1 t2 - 1>Z +X i2 ("-*). 1} 



can be obtained, where h' = h - 1 = 0. 
Since 



(k) (k) (k) 

1 Cg^^-l] 

is an Abelian group from Remark 6.2 whose generators (i.e., bases of the 
Abelian group) are |< k > , (« |W l« ... tj^j, 

u ° > +il + - + V n - k) -i^ + i , >, (7ao) 

. (n) + u ( "> V /(n) \ /(n) (n) 

(n) 

(n-k-1) 

d +1 fn.lr.l , 



-7k- 



can be obtained. 



Since u' n is the column vector of U , the elements of (u^ + u^ 
x n \ i 

are or 2, I.e., non-negative in general. Therefore, letting 



P \ 



the right-hand side of Eq„ (7.10) 



\ X N-1 / 



(7.11) 



x. > 
l — 



(7.12) 



can be obtained for any i(0<i<(N-l)) 
From Eq. (7.9) and Eq. (7.H), 



V Q = (h',!^.,,,!^) 



"N-l, 



= Vo + h l X l + ••• + Vl X N-l (7 ° 13) 



can be obtained. 

Therefore, when V = holds, 



h. = 

1 



rhen x. f 

1 ' 



can be obtained from Definition 3.2, Eqs. (3. 5) and (7.12) 
Now, from Eq. (7.8), 



(7.14) 






V i = X \ + A 'k + '•• + X ' (n-k) k 



2 'N(jei L ) 



{2 (n ~ k) -l} 



= (h',^,...,^) u + 



(n) „(n) 



+ „ „ . + u 



2 +(jei 1 ) 



(n) 

(2 (n - k) -l}2 k + Uei ) 

(2 U kj -l] 



= (h^,...,^) 



(n) 



u + u + ., 

2 K± 1 



+ u 



{2 (n-k)_ 1)2 k + . 



» u 



(n) 



[2 (n-k)_ 



(h^,...,!^) 



/ X ° \ 



(n) 

u . 
J 



X 



N-l 



(from Eq. 7.10) and Eq. (7.11) 



X U 0j 



= (h^h^^h^; 



x,u, . 
1 lj 



X N-l U (W-l)j 



h X U 0j + h l X l U lj + -° + Vl) X (N-l) U (N-l)j 



= (from Eq. (7.14)) 



can "be obtained, 



Now, in the solution of VA'V = such that the number of most efficient 



codes is 2 , 



det V Q £ 



can be obtained- Therefore, from Eq. (7.2), 



A + A 1 A 1 A 1 + A 2 A 2 A 2 + ' 



-76- 



A {2 (n - k) -l} A {2 (n - k) -l} A (2 (n - k) .~l} 



= 



can be obtained. Therefore, from Eq. (7.15) and Eq„ {7.7), 



(7.15) 







(2 k -l) 



(7.16) 



can be obtained. 

Therefore, the problem can be reduced to that of obtaining maximum k 
such that Eq, (7.l6) holds, Accordingly, from Theorem 7.1 the problem can be 
reduced to that of obtaining maximum k such that V = 0. 



Theorem 7-2 . The problem of obtaining maximum k such that V = can be reduced 
to obtaining a solution in non-negative integers x, , x , . .., x , k, for the 



equations 



\„ + x, X' + x„\ 



1 r 1 2 (r 1 +r g ) 



. + x \, \ 

n ( r, +r^+„ . „+r ) 
12 n 



(7.17) 



1 + x n + x^ + „ . „ + x =2 
12 n 



(n-k) 



(7.18) 



which maximizes k where 



-77- 



(I) when k > (n - k) 



1 - n-k 1 



1 2 - n-k 1 n-k 2 



X l + X 2 + 



+ x , < , C i + i C o + 
n-k — n-k 1 n-k 2 



x, + x„ + . . . + x . . < 2 
1 2 n-k+1 - 



(n-k) _ 



x 



(n-k) + 



+ x < . C n 

n — n-k n-k 



^ 



+ vC > - 2 (n " k) - : 

n-k n-k 



o( n -k) -, 
X] _ + x 2 + . . . + x k+1 < 2 - 1 



x + x + ... + x. . + x, _ < . C + C_ + . .. + C . 

2 3 k+1 k+2 - n-k 2 n-k 3 n-k n-k 

x, + ... +x. . +x, , < ,C. + , C, + . „ „ + C . 

3 k+2 k+3 - n-k 3 n-k k n-k n-k 



> (7.19) 



J 



■78- 



(II) when k < (n - k) 



1 — n-k 1 



x, + x_ < .C. + C_ 

1 2 — n-k 1 n-k 2 



x. + x + x_ < C. + ,C. + . C_ 

1 2 3 ~~ n-k 1 n-k 2 n-k 3 



X l + X 2 + 



+ x. , < . C n + .C. + 

k+1 — n-k 1 n-k 2 



+ n-k C k+l 



X 2 + 



+ x. , + x. _ < . C + , CL + . . . + , C. _ 

k+1 k+2 - n-k 2 n-k 3 n-k k+2 



x 3 + 



+ x. _ < . C_ + . . o + , C. _ 
k+3 _ n-k 3 n ~k k+3 



x _. + . . . + x . < . C _.+...+ ,C 

n-2k n-k — n-k n-2k n-k n-k 



n-2k+l n-k+1 — n-k n-2k+l n-k n-k 



^ 



V 



(7.20) 



x ,+...+ x < ,C . 

n-k n — n-k n-k 



J 



and where 



and 



r\= 2 , r_ = 2 , . . . , r , = 2 , r =1 

1 '2 n-1 n 



:, f x , ..., x are non-negative integers 



Remark 7.1. Equation (7-17) is an indefinite equation of n variables (x v x , 



1' 2 ; 



.... x ) of the first order. Therefore, the general solution can be always 
7 n 



i:ied. First, obtain a bo1u1 ion for maximum k L] tie general solution bui 
that Eq. (7«l8) is satisfied. Then the conditions, i.e., k>n-kork<n-k 
are determined. Next, investigate whether the solution satisfies Eq. (7.19) 
or Eq. (7.20) corresponding to the conditions k > n - k or k < n - k, respectively. 
If the solution does not satisfy Eq. (7. 19) or Eq. (7=20), obtain the solution 
about the next maximum k in the general solution such that Eq. (7»l8) is 
satisfied. 

Continuing the precedure, the solution for maximum k such that 
Eq. (7ol8) and Eq. (7. 19) or Eq. (7.20) are satisfied, can be obtained. 
This is the desired solution. 

Proof of Theorem 7.2 . In V (cf. Eq. (7-8)), since < ± ± < 2 - 1 (cf. 

Eq. (7°5))> there exists a possibility that A' = A' or A' , or . ,., 

2 +i 1 r l r l +r 2 

or A (cf. Theorem 4.4). A similar possibility exists with respect 

r +r +. . .+r 
r l 2 k+1 

to X ,, , \ , A' / \ ,„..,A'/ \ . Therefore, the number of 

(,K+±J [k+d) (,n-±J . 

2 +1 2 2 +1 2 2 2 +1 2 (n-k-l) 

A' having the possibility is , C, . 

n-k 1 

Next, there exists a possibility that A' = A or A' 

3'2 k + i r l +r 2 r l +r 2 +r 3 

3 

or .... or V A similar possibility exists with respect to 

r +r +„ . . +r 
1 2 k+2 



A' , A , ..,, and the number of A 1 which has the possibility is C 
1- r^k . /■ „k . n-k 2 

6-2 +i 6 

Continuing the discussion, Fig. 7=1 and Fig. 7.2 can be obtained 



5-2 +i c 6-2 +l c 
5 o 



corresponding to k > n - k and k < n - k, respectively. 

In Fig. 7.1 and Fig. 7.2, (i) and (i)2 + j mean, respectively, 

A' and A' , 

r, +r +. . .+r . / ^k . 

12 1 (r +r +. . . +r. J 2 +j 

As shown clearly in Fig. 7.1 and Fig. 7.2, the conditions (7.19) and 
(7.20) can be obtained corresponding to k > n - k and k < n - k, respectively. 
Equation* (7.17) is also satisfied. 



-80- 



, , k (D(2)(3) 

(1)2* + i 

(2)2 k + i 
(3)2 k + i 



(n-k)2 K + i 




X l X 2 x 3 



"n-k 



L k+1 



Figure 7.1. (k > (n - k)) 



(1)2 K + i 
(2)2 k + i 
(3)2 k + i 



(1)(2)(3) (n-2k) (k) (k+1) (n-k)(n-k+l 



(n) 



(k + l)2 K + i 



(n- k)2* + i 




Figure 7-2. (k < (n - k)) 



-81- 

Since the number of terms of the right-hand side of Eq. (7*8) 
2 (n-kJ^ it is ciear that Eq> (7.i8) must hold. 

Now, suppose that maximum k and x , x , „ . . , x such that Eq. (7.17)* 
Eq. (7.18) and Eq. (7.19) or Eq. (7-20) are satisfied, have been obtained. 
From Eq. (7.19) and Eq, (7/20), 



x n < . C, 

1 - n-k 1 



holds. Therefore, x, of the elements \\ , X ' . , X\ _. ,..., 

1 o k • o k+1 • n k+2 • 

2 +i, 2 +i 2 +i 

2 

\' / , \ , can take the value \' . It is quite arbitrary which of them 

2 (n-k-l) 

take the value A,' . 
r l 
Therefore, let x, of them take the value A,' . 
1 r l 

Next, let x of the others whose number is ( , C, - x, ) and \' , , 

(— n— K -L -L A 

3°2 +i 

A.' , . . . , in general A, 1 , take the value A' . Since 
5°2 +i (2)2+1 r l +r 2 



x, + x_ < , C. + C_ 

1 2 — n-k 1 n-k 2 



holds from Eq. (7.19) & n( 3- Eq. (7.20), the procedure is always possible. 

Continuing such a procedure (it is always possible since Eq. (7.19) 
and Eq. (7.20) hold corresponding to k > n - k and k < n - k, respectively and 
Eq. (7.18) holds), the value of each term of the right-hand side of Eq. (7.8) 
can be determined and V = holds from Eq. (7.17) ° Then, of course, i, , i , 



V 



., can also be determined, 



Remark 7 » 2 . The values of i, , i , ..., can be determined as shown in the proof 
of Theorem 7.2. 
Since 



-82- 



V n = V.A. 
J J 



holds for any j (0 < j < 2^'^ - l) from Eq. (6.7), 



C = C = C 
° V.i. J £ * + i. 

J J 



(7.21) 



can be obtained from Theorem 6.7, 

Therefore, from Eq. (7.21) 



^ 



JS +(i.el) 

J 

2 k 

J2%(i ®2) 

J 



> 



2 k -l j2 k +{i e(2 k -l)} 



(7.22) 



can be obtained. Therefore, 



j2 +i. 



J j2 k +(i.©l) 

J 



= z 



j2 +(i e2) 

J 



1 



Z =7 

2 k -l j2 k +{i.e(2 k -l)j 
J J 



(7.23) 



can be obtained. 

Now, from Theorem 3.1 and Eq. (3.27), 



-83- 



ZA'Z = U 



U A'U 

n n 



vj 



u 



k N-l 



/ X 



= u 



(H(n,p) - E N ) 



k N-l 







x 



N-l 



U 



= 



Accordingly, 



/ x. 



(H(n,p) - E N ) 



U-l 







= 



(7.24) 



Hf-1 



can be obtained „ 



.(n) 



T 



Equation (7.24) means that when x. is identically zero, u^ 11 £ V 

(n) T "" 

and when x. is not identically zero, u. e V, 
l i 

On the other hand, applying (Theorem 2.1) to Z, 



x. =>Tw (vv-" z N-i )u i 



(n) 



(7.25) 



can be obtained, for any i(0<i<N-l). 

Therefore, it is possible from Eq (7.23) and Eq. (7.25) to find 



.(n) 



such that 



■8k- 



u. n) £ V. when x. £ 
11 l r 



u' n ^ jt V. when x. = 
1 i i J 



(7.26) 



Therefore, all the codes corresponding to the binary expression of i such that 
x i ^ are the set of most efficient codes under the conditions. 



Remark 7.3 . In general, 2 < the number of most efficient codes < 2 n_P+1 holds 
(cf. Y. Komamiya: Bulletin of Electrotechnical Laboratory, Vol. 17, pp 298-3IO, 
1953 and Proceedings of the Third Japan National Congress for Applied Mechanics, 
195*0- Therefore, letting K Q be a maximum k, 

1 5 K 5 n - P + ! (7*27) 

can be obtained. 



Remark 7.4 . When there exist A , A , ..., A , v satisfying Eq. (7.15), 

d (2 ln " iJ -l) 

+ A , + A .., + A , x also clearly satisfy Eq. (7.15). 
2 {2 ln ~ RJ -l) 



Example 7.1 . The case of n = 3, p = 2. 

From Theorem k-.k and Theorem 4.6, 



\>- 


k 


A. 

r l 


2 


X 
r i +r 2 





\ 

r 1+ r 2+ r 3 


-2 



•85- 



Accordingly, 



"\ 



*0" 3 



\' = 1 



T +T 

12 



r l +r 2 +r 3 



= -1 



= -3 



(7.28) 



J 



*0-3 



K =X 2 =X h =1 



3 5 6 



V" 3 



(7.29) 



can "be obtained. 

Applying Theorem 7-2 to this case, 



>v 



3 + x 1 - x 2 - 3* 3 = 



1 + x, + x + x_ = 2 



J 



(7.30) 



From Eq. (7-27), 



k<n-p + l=3-2 + l = 2 



can be obtained. 

Now, let k be 2, i.e., 



■86- 



k = 2 



(7-31) 



Therefore, from Eq. (7-31) and Eqs. (7. 30), 



X l " x 2 " 3x 3 + 3 = ° 



-\ 



X l + X 2 + x 3 " X = ( 



x 3 = l 



X l = x 2 ■ " ° 



can be obtained. From Eq. (7.31), 



k = 2>n-k=3-2 = l 



(7.32) 



k > n - k 



(7.33) 



can be obtained. 

It is shown below that Eqs. (7.32) satisfy Eqs. (7.I9) 



X l = 



X-, = 



X l + X 2 



X l + X 2 + x 3 
x 1 + x 2 + x 3 



°-S c i 

< 2 n ' k -1=2 

< 2' -1=1 

1 < 2' -1 = 1 



1 5 i c i " x 



"\ 



-1 = 1 



J 



Therefore, since 



t2 (n " k) -l) X 



4 = 3 



(7.3i*) 



-87- 



can be obtained. Therefore, from (7-23)> 



z = Z 7 



-\ 



Accordingly, 



z l " z 6 



\* z 5 



Z_ = Z, 
3 ^ J 



X 



(7-35) 



can be obtained. Therefore, from Eqs. (7-35) and Eq„ (7.25), 



x = V8 



x, = -f~8 



x £ = ^8 



x -^8 



x, = -Jq 



x = ^8 



= ^8 



X 7 = 



z Q + z x + z 2 + ... + z ) = 2vT8 (z Q + z 1 + z 2 + z ) ^ 



z " z l + z 2 ' z 3 + z 4 " z 5 + z 6 " z 7 } = ° 



z + z l ' z 2 " z 3 + \ + z 5 " Z 6 " z 7 } = ° 



z " z l " z 2 + z 3 + z 4 ' z 5 " z 6 + z 7 } = ^ (z ' z l " z 2 + z 3 } ^ ° 



z + z l + z 2 + z 3 - \ - z 5 ' z 6 " z 7 } = ° 



z " z l + z 2 " z 3 " \ + z 5 " z 6 + z 7^ = ( z - z x + z 2 - z^) ^ 
z + z l " z 2 - z 3 " \ - z 5 + z 6 + z 7 } = ^ 8 U + z l " z 2 " z 3 } ^ ° 



z " z l ' z 2 + z 3 " \ + z 5 + z 6 ' z 7 } = ° 



can be obtained. Therefore, x n ^ 0, x ^ 0, x ^ 0, x-r ^ can be obtained, 
Therefore, the most efficient codes are 



-88- 



[° 











1 


1 


1 





1 


1 


1 






(7=36) 



Example 7*2 . The case n = 3> P = 3 

From Theorem k.h and Theorem h.6, 



K^6 



\ 



r. 



r +r 
12 



A.' 
r +r +r 
12 3 



= 



> 



= 



J 



(7.37) 



can be obtained „ From Eq. (7-27), 

1 <k< 3 - 3 + 1 = 1 

can be obtained. Therefore, in this case, k = 1 can be obtained. 
Applying Theorem 7.2 to this case, 



6 + x 1 * + x (-2) + x • = 



1 + x + x + x = 2 = ^+ 
J- <- j 



x l " x 3 " ° 



x 3 = 3 



"\ 



(7.38) 



(7.39) 



can be obtained. 



-8 

Since n-k=3-l = 2 and k = 1 hold, k < n - k can be obtained. 
It is clear that Eq. (7-39) satisfies Eq. (7.20). 
From Eq. (7-8) 



1 2 +i 2 J 3 



can be obtained. Therefore, from Eq. (7. 39) t 



\ 



2 + i 1 = 3 



2 + i 2 = 5 > 



3-2 + i = 6j 



Accordingly, 



•i- 1 



Si" 1 



i 3 = o 



can be obtained. Therefore, from Eq. (7.23), 



z o = z 3 = z 5 = Z 6 



z l = z 2 = z 4 = z 7 



(7.1*0) 



can be obtained. 

Therefore, from Eqs. (7.U0) and Eq. (7.25), 



■90- 



x ^0 



x ? f 



"\ 



\ 



x l = x 2 = x 3 = \ = x 5 = x 6 = ° . 



(7A1) 



can be obtained. Therefore, the most efficient codes of this case are 



'0 

a i i, 



(l.h2) 



8. GENERAL SOLUTION OF VA'V T = 



Since 



Z = -i (1,1,. ..,1)6 

VN 



(8.1) 



holds from Definition 3-6, 



(n) 



.(n) 1 



= vN (z_, z, , . . ., z_ T n )u. = 1 when uY 

Cr 1 N-l i l 



:. -Vm (z ,z 1 ,...,z n _ 1 )u^ = when u[ n) ft V 



> (8.1') 



v 



can be obtained, where 



/ x r 



Z = U 



u 



x 



N-l 



(cf. Definition 3.7). Therefore, 



x Q = x ± + . . . + x = m 



(8.2) 



can be obtained where m is the greatest possible number of most efficient codes 
Since 



z ^(i,i,...,iK , 



z o = 



m 
n/n 



(8.3) 



can be obtained. 



-91- 



-92- 

Now, the discussion from Eq. (7-24) to Eq. (7.26) holds in general. 

Therefore, letting the number of x. such that x. - be a, 
7 ° l l 

m = N - a (8.4) 

can be obtained. 

Since each z. for any i (0 < i < N - l) can be expressed as a linear 
combination of x fi , x-,, . .., x , from Eq. (8.1), "a" elements of z , z,, . .., 

z can be considered the independent variables. 

From Eq. (8.4), in order to let m be a maximum, it is necessary to 
let a be a minimum, that is, 

max(m) = N - min(a) (8.5) 

Now, let the relation among z , z , ..., z obtained from Eq. (3«27)> 
i.e., ZA'Z = be 

R or R or R or ... (8.6) 

If the relation in which the number of independent variables among 
z , z , z , ,.., z is a minimum is selected among the relations R , R , 
R , ..., the number is max(N - a), i.e., max(m). 

Example 8.1 . The case n = 3> p = 2 

This case is Example 7-L Here, the case will be solved by the 
method developed in this section. 

From Eq. (7.29), 



-93- 



s> 



' 3 



\ 



X i = K " K ■ x 



S " S " ^ " - 1 



>• 



*} - -3 _ 



holds. Therefore, from the equation ZA'Z = 0, 



Vl " Z 6 Z 7 



z o z 2 = Z 5 Z 7 



< 



Z Z 3 = \ z l + Z 5 Z 6 ' z l z 2 



Z Z 4 " Z 3 Z 7 



Z Z 5 " Z 2 Z 7 + Z 3 Z 6 " z l z 4 



Z Z 6 = z l z 7 + Z 3 Z 5 " Vk 



r 



z l z 3 = V< 



< z l z 5 = Z 2 Z 6 



v. 



Z 2 Z 3 = V 5 



(8.7) 
(8.8) 

(8.9) 

(8.10) 

(8.11) 

(8.12) 

(8.13) 

(8.14) 

(8.15) 



. 9 k- 



r 



3( Z ; 



2, 2 2 2 

Zy) + z i + z 2 " 



It 



f 2 2 2, . 

^ z 3 + z 5 + z 6 ) = 



3(z 



2x 2 2 2 

" z ^ - z 3 + z^ 



1 " V + z o 



< 



^/ 2 2x 2 2 2 

3(z 2 - z 5 ) + z 3 + z Q + z 6 



,2 2 2v 

^ Z 2 + \ + v 



(2 2 2, 

(z l + z 7 + V 



v 



nt 2 2v 2 2 2/2 2 2-. 

3(z 3 - z^) + z 2 + z x + z - (z Q + Zg + z J = 



(8.16) 



= (8.17) 



= (8.18) 



(8.19: 



can be obtained, 

Substituting (8.7), (8.8), (8.10) in (8.9), 



(1 - 



#<v 3 



v< 



= 



(8.20) 



can be obtained, Similarly, substituting (8.7), (8.8), (8. 10) in (8. 11) and 
(8.12), 



(1 



~I )(z z 5 
z o 



z 3 z 6 ) = 



(8.21) 



(1 



z o 



z 3 z 5 ) 



= 



(8.22) 



respectively can be obtained. 

From (8.20), (8.21) and (8.22), 



/r s 2 2 

(I) z ? = Z Q 



I 






I 



V 3 = Z 5 Z 6 



Z Z 5 = Z 3 Z 6 



^ Z Z 6 = Z 3 Z 5 



(8. 

(8.2*0 

(8.25) 



can be obtained. 

From (II), 



3 2 2 2 

V 3 Z 5 Z 6 = Z 3 Z 5 Z 6 



Z 3 Z 5 Z 6 (z 3 Z 5 Z 6 ' z } 



= 



can be obtained, Therefore, 



ll. l) ^5 Z 6 = 



or 



(II. 2) z^z 



6 = Z 



can be obtained, 



In (11,1), when z = 0, from (8.24), (8.25), 



z 5 = z 6 = ° 



can be obtained. Similarly whe z,_ =0, z^ = z r = can be obtained, and when 

5 3° 

z^ =0, z = z = 0, Therefore, when (ll.l), 



z 3 = z 5 = z 6 = ° 



(8.26) 



can be obtained. Therefore, from (8.7), (8.8) and (8.9), 



-96- 

z l = z 2 = \ = ° (8=27) 

can be obtained. Therefore, from (8.16), 



2 2 
Z 7 = Z 



can be obtained. Therefore, (II. l) can be reduced to (i). 

Therefore, only the cases (l) and (11.2) may be analyzed, 

(i) The case z_ = z 



holds. 



(1.1) When z ? = z Q 



Z 7 = ± Z 



z l = z 6 (8-28) 



z 2 = z 5 (8.29) 

\ = z 3 (8.30) 

can be obtained. These relations, i.e., z ? = z Q , (8.28), (8.29), (8.3O) clearly 
satisfy the relation (8.13) to (8.19). Therefore, in this case, the number of 
independent variables among z Q , z ± , . .., z is 4. Therefore, the greatest 
possible number, i.e., max(m) = k can be obtained. 

As in Example 7.1, using the relations z = z , (8.28), (8.29), (8.3O) 
to 

*j =^N (z , Zl ,...,z 7 )u. 
x = lf x 3 = 1 ' x 5 = 1 ' x 6 = ^ x i = x 2 = x 4 = x 7 = ° 






can be obtained. Therefore, the most efficient codes are 



JO \ 















1 


1 


1 





1 


1 


1 






(1.2) z ? = -z Q 



From (8.7), (8.8), (8.10), 



z l = " z 6 



^ 



Z 2 = " z 5 > 



\ = " z 3 



J 



(8.31) 



can be obtained. These relations, including z_ = -z , clearly satisfy the 
relations from (8.13) to (8.19). Therefore, in this case, the number of 
independent variables among z , z , ..., z 7 is h. Therefore, the greatest 
possible number, i.e., 



max(m) = h 



can be obtained. 



From z = -z and (8.31), similarly 



x l ~ x 2 ~ x k ~ x 7 " - 1 



x,-, — x~ ■• X,- —■ X/- ~" u 

0356 



can be obtained. Therefore, the most efficient codes are 



-98- 









1 





1 





1 








1 


1 


1 



(II. 2) The case z z n z A = 

3 5° 



From z z z^ = z n and (8.23), 



3=3 
Z Z 3 " z o 



3 2 
Z 3 = Z 



C" Z = ~f> (Cf. Eq. (8.3))) 



(8.32) 



can be obtained. Similarly (8,24) and (8.25), 



2 2 2 2 
Z 3 = z 5 = z 6 = z o 



(8.33) 



can be obtained. 



On the other hand, from z^z^z A = z^ > ( ' . * z„ = — > 0) 

3 5 6 ^ 



z > 



\ 



"\ 



z 3 >0 



z 6 >0 y 



z r < . 
6 y 



*\ 



z 3 <0 



. > y or z,_ < r or z._ > Y 

5 [ 5 1 5 



z r < 
6 ^ 



> 



V 



z < o ; 



z g >0 



y 



must hold. Therefore, 



z 3 = z 5 = Z 6 = z 



or 



■"•'- 



z 3 = " z 5 = z 6 = z 



or 



" z 3 = Z 5 = " z 6 = z 



or 



" z 3 = " z 5 = z 6 = z 



can be obtained. 

Therefore, from (8„7)> (8.8), (8.9) and the above relations, 



or 



or 



or 



Z l " z 2 " \ ~ T r Z 3 " Z 5 " Z 6 " Z 



Z l " Z 2 " ~\ ~ ~ Z T Z 3 " " Z 5 " " z 6 " Z 



" z l = Z 2 = -\ = V " Z 3 = Z 5 = " Z 6 = Z 



z, = -z^ = -z, = z„, -z„ = -z r = Z A = z 



1 - * 2 " h " "7' 3 ' 5 " 6 " "0 



can be obtained. These relations also satisfy the relations from (8.I3) to 
(8.I9). Therefore, in these cases, the number of independent variables amon£ 
z , z , . . . , z is 2. Therefore, the greatest possible number, i.e.^ 

max(m) = 2 

can be obtained. 



-100- 

Calculating x ± = VN (z Q , z^ . . . ,z )u. by using these relations, the 
following results can be obtained: 

o\ /l \ /0 1 0\ / 1 
i i i/, \0 1 1 / , \l 1/ , \ 1 1 

Finally, max(m) = 4, the greatest possible number, that is (i.l) and 
(1.2), can be obtained. 



9. GENERAL SOLUTION OF VA'V T = IN APPLICATION OF BOOLEAN ALGEfc 

T 
A necessary and sufficient condition that VA'V = is that 

x.x.h. . = (9.1) 

i J i®J 

when i ^ j (0 < i, j <* 2 n - l), and that x 2 h' = for < i < 2 U - 1. 

2 
Equation (9.1) follows from Eq. (7.24), and x.h' = because h' = 0, 

Since x. = 1 or holds for any i(0<i<2 n -l) from Eq, (8.1 1 ), 

x. can be considered as a variable of a Boolean function. 

l 

In order to satisfy Eq. (9.1). when h. . = 1, x.x. = must hold, but 

lej ' l j 

when h. . = 0, the value of x.x. may be arbitrary. 
i©j i J J J 

Therefore, when h. . = 1. 
lej 

x ± x. = (9,2) 

.'. 7, v y . = 1 (9-3) 

J 

must hold for any i / j (0 < i, j < 2 - l), where y. is a negation of x., 



"N 



y. = x: 

^i i 



> (9.4) 



y. = x 

J 



Therefore, 



0<i 


,j<£ n - 


-l 












n 




(*i 


\s 


V 


= 1 


h. 
i 


.=i 













(9.5) 



-101- 



-102- 



must hold. Therefore, after the expansion of Eq. (9»5)> choose the term whose 
number of variables (y.'s) is minimal. 
Now, suppose that the term is 

y, y, ...y, (9.6) 



Then if 



y, y, ...y, - i (9-7) 

X l X 2 ^ 



holds, 



y, - y, = ... = y. = l (9.8) 

x i x 2 ± i 



can be obtained. Therefore, from Eq. {9 .h) and Eq. (9-8), 



x. = x. = ... = x. =0 (9.9) 

X l X 2 H 



can be obtained. This means that ifx. =x. = ... = x. =0, 

X l X 2 H 



VA'V T = 



can be obtained, where I is the minimum number of Boolean variables among terms 
in the expansion of Eq. (9.5) whose Boolean variables are equal to zero. 
Therefore, put x. = 1 for any i (0 < i < 2 -l), where 

i / \> i t i- 2 ' '"' i ^ ± £ 

Then, the greatest possible number of most efficient codes is 

(N - £) (9.10) 



-103- 



and the most efficient codes consist of the binary codes corresponding to a; 



(0 < i < 2 n - 1) for 1 / i,, i / i oJP ..., i / 



V 



Remark 9 ■ 1 - Without loss of generality, u € V can be assumed. Therefore, 



x. = 1 can be assumed, 



Example $.1 . The case n = 3> P = 2 
From Example 3»3.> 



h' = 0, b. = h = h, = 1, h = h = h. = h = 







l " 2 "' 1* "' ' 3 5 "" 6 "' 7 



can be obtained. Therefore, from Eq„ (9*2) 



X X 1 



X X 2 



x o x u 



X 1 X 3 



X 1 X 5 



X 2 X 3 



X 2 X 6 



X 3 X 7 



x h x 5 



x k x 6 



X 5 X 7 



= o ^ 



= 



= 



= 



= 



= 



= 



= 



= 



= 



= 



> 



(9.11) 



x 6 x ? = J 



-101+- 



can be obtained. From Remark 9.1, 



(9-12) 



*o = 1 

holds without loss of generality. Therefore, from Eq. (9«5)> 

y 1 y 2 y i+ (y 1 v yJ(y x v y^)(y 2 v y 3 )(y 2 v ygKy^ v y ) 
• (y^ v y 5 )(y J+ v y^)(y 5 ^ y 7^ y 6 v y 7^ = 1 

can be obtained. Therefore, 

Eq. (9 = 12) = y 1 y 2 y i ^(y 1 v y^Hyg v y 3 y 6 )(y 3 v y^)(y J+ v y^Ky y 6 v y^) 

= y 1 y 2 y 1+ (i v y^H 1 ^ y^)^ ^ y^)(i v y 5 y 6 )(y^y 6 v y ? ) 

= y 1 y 2 y i ^(y 3 v y 7 )(y 5 y 6 v y^) 

= y 1 y 2 y i+ (y 3 y 5 y 6 v y ? ) 

= y 1 y 2 y i ^y 7 v y^ 2 y y f h y 3 v G (9.13) 

The term of the right-hand side of Eq. (9.I3) whose number of 
variables is minimal is 

y ]_ y 2 y 4 y 7 

Therefore, the greatest possible number of most efficient codes is 2 - k = h. 
Therefore, 

y 1 y 2 y i+ y ? = i 

can be obtained. Therefore, 



-105- 



x l_ = x 2 = \ = X Y " ° 



Accordingly, 



x " x 3 " x 5 " x 6 " 1 



can be obtained. Therefore, the most efficient codes are 



° 











1 


1 


1 





1 


ll 


1 






10. CONCLUSION 

Most efficient codes were found in principle by the methods discussed 

above . 

Now, define m , m , m as follows: 
GOO 

m : the number of most efficient group codes 
G 

m : the number of most efficient codes under Condition 6.1 and Condition 6.2 
m : the number of most efficient codes in general 



From the description of Section 7 and Remark 7° 3* 



2 < m_ < m_ < m_ < 2 n_P+1 (10. l) 

G L (J 



can be obtained. 

As a future problem, do there exist most efficient codes under 

Condition 6„1 and Condition 6.2 such that m > m_? Another problem is to 

G 

obtain an elegant method of solution for general most efficient codes such that 

m o > V 

This paper has presented a new conclusion, that the most efficient 
codes problem under Condition 6.1 and Condition 6.2 including group codes has 
been solved completely. 



-106- 



1/ 



M 2 a tm